Problems & Puzzles: Puzzles

Puzzle 199. The Prime-Vampire numbers

According to Clifford A. Pickover vampire numbers (VN) are integers n = x y such that n contains the same digits as x and y. The integers x and y are called the fangs of n. True vampire numbers need that the digital length of the two fangs are the same and no both end in zeros.

  • The smallest example of a 2-fangs VN is: 1260 = 21 x 60

Extending the idea to more than two fangs:

  • The smallest example of a 3-fangs VN is: 197925 = 29 75 91

We will define for this puzzle that Prime Vampire Numbers (PVN) are Vampire Numbers such that its fangs (factors) are prime numbers.

  • The least example of a 2-fangs PVN is: 117067 = 167x701
  • The least example of a squared PVN is: 2459319153459529 = (49591523)2

Questions

  1. Find 10 more squared PVN
  2. Find the least PVN= (fang)^k, for 6=>k=>3
  3. Find the least PVN with k distinct fangs, for k = 3 & 4
  4. Find a semi-titanic (500 digits) PVN

_____
Vampire Numbers, Web References:
Eric Weisstein, Walter Schn
eider, John Childs & J. K. Andersen


Question 1 was solved by J. K. Andersen, J. C. Colin and Sudipta Das. Questions 2, 3 & 4 was solved only by J. K. Andersen.

***

Question 1. Here is the S. Das's list who got the earliest 15 PVN's:

The first 15 squared PVN s are :

   2459319153459529 = 49591523 ^ 2 ( the example given above )
   2512099504480801 = 50120849 ^ 2
   3395758728913321 = 58273139 ^ 2
   3893627338729969 = 62398937 ^ 2
   5129508768706921 = 71620589 ^ 2
   8186379410403769 = 90478613 ^ 2
170147428389340249 = 412489307 ^ 2
189598345243224241 = 435428921 ^ 2
271971550510512889 = 521508917 ^ 2
334573968623758249 = 578423693 ^ 2
571691675535320209 = 756102953 ^ 2
577337986280725609 = 759827603 ^ 2
842769461809107121 = 918024761 ^ 2
918564378413675449 = 958417643 ^ 2
968781726110944201 = 984267101 ^ 2

***

Question 2 was solved by J. K. Andersen:

Proof that PVN = (fang)^k has no solutions for k=3,4,5,6, 7 & 9:

Assume a PVN solution c = a^k for some k>1 (not necessarily in {3,4,5,6}) By definition, the digits of c is the digits of a repeated k times in some order. This implies:

d(c) = k*d(a), where d(n) is the decimal digit sum of n.

Let mod be the infix modulo operator as in 24 mod 9 = 6. c = a^k implies: c mod 9 = (a mod 9)^k mod 9

d(c) = k*d(a) implies: d(c) mod 9 = ( k*(d(a) mod 9) ) mod 9

c mod 9 = d(c) mod 9 is true for any c.

Apply this to the above equations and combine them:

(a mod 9)^k mod 9 = c mod 9 = d(c) mod 9 = ( k*(d(a) mod 9) ) mod 9 = ( k*(a mod 9) ) mod 9

Let b = a mod 9 and we have the equation: b^k mod 9 = (k*b) mod 9 Or in another notation: b^k == k*b (mod 9), where b<9. b=0 is always a solution but this implies that 9 divides a, so a is not a prime. The other solutions for small k are:

k=2: b=2
k=3: b=3 or b=6
k=4: No solution
k=5: No solution
k=6: b=3 or b=6
k=7: No solution
k=8: b=8
k=9: b=3 or b=6
k=10: b=1 or b=4 or b=7
 

b = a mod 9, so b=3 or b=6 implies that 3 divides a, and a is not a prime (unless a=3 but 3^k is never a PVN). The three smallest k without prime solutions ruled out this way are: k=2, for b=2 k=8, for b=8 k=10, for b in {1,4,7}

It has now been proven there are no PVN for k = 3,4,5,6 (and 7,9). Note that if a^2 is a squared PVN (k=2) then a mod 9 = 2. This can speed up the search for squared PVN. I have not searched PVN for k=8 or k=10 and don't know whether they exist. Finding or disproving solutions could be a follow-up puzzle but may be hard.

***

Question 3 was solved by J. K. Andersen:

There are no PVN with 3 fangs. Proof: Assume vampire number (not necessarily PVN) n=a*b*c

By similar computations as previously, it can be shown that: a*b*c == a+b+c (mod 9) This means (a mod 9, b mod 9, c mod 9) must be one of these:

(0,0,0),(0,1,8),(0,2,7),(0,3,6),(0,4,5),(0,5,4),(0,6,3),(0,7,2),(0,8,1), (1,0,8),(1,2,3),(1,3,2),(1,5,6),(1,6,5),(1,8,0), (2,0,7),(2,1,3),(2,3,1),(2,4,6),(2,6,4),(2,7,0), (3,0,6),(3,1,2),(3,2,1),(3,3,3),(3,4,8),(3,5,7),(3,6,0),(3,7,5),(3,8,4), (4,0,5),(4,2,6),(4,3,8),(4,5,0),(4,6,2),(4,8,3), (5,0,4),(5,1,6),(5,3,7),(5,4,0),(5,6,1),(5,7,3), (6,0,3),(6,1,5),(6,2,4),(6,3,0),(6,4,2),(6,5,1),(6,6,6),(6,7,8),(6,8,7), (7,0,2),(7,2,0),(7,3,5),(7,5,3),(7,6,8),(7,8,6), (8,0,1),(8,1,0),(8,3,4),(8,4,3),(8,6,7),(8,7,6)

They _all_ have at least one 0 or 3 or 6. The corresponding fang is divisible by 3 and cannot be a prime. Example: Vampire number 197925 = 29*75*91 (29 mod 9, 75 mod 9, 91 mod 9) = (2,3,1). b mod 9 = 3 implies that b (=3*5*5) is divisible by 3.

...

PVN with 4 fangs cannot be ruled out this way and I will search for them. They must satisfy a*b*c*d == a+b+c+d (mod 9). This has many solutions without 0, 3, 6.

In all cases here, I only consider PVN with distinct fangs.

It took a few seconds running with limited optimizations to find all 40 solutions with 3-digit fangs. The only one containing all 10 digits is: 541*607*883*929 = 269378154809 This one has 5 7's: 421*607*773*877 = 173240677787

The complete list:

379*409*677*991 = 103997964977
229*683*751*907 = 106537722899
347*463*751*907 = 109435364777
313*647*691*811 = 113487366911
409*523*631*929 = 125392069493
421*599*601*829 = 125642890991
467*523*631*823 = 126837526433
281*727*739*853 = 128775783329
251*643*823*997 = 132427959683
349*619*631*983 = 133998196463
313*643*733*911 = 134393313617
277*617*883*907 = 136877770829
353*613*739*859 = 137363953589
331*641*787*823 = 137423368871
409*541*719*883 = 140478598913
487*523*643*881 = 144283786583
439*541*673*911 = 145611349397
367*619*811*857 = 157891368671
409*601*761*859 = 160685097491
421*613*673*947 = 164477923163
421*607*773*877 = 173240677787
433*601*691*971 = 174606193913
421*653*733*877 = 176725347833
499*571*727*863 = 178764739529
409*601*857*859 = 180955490867
439*547*811*953 = 185594713439
397*607*857*919 = 189790963757
419*739*751*829 = 192775984139
421*587*853*919 = 193724585189
547*601*647*919 = 195470664971
577*613*647*859 = 196577465873
523*571*829*929 = 229989517253
409*743*823*997 = 249348703997
541*607*883*929 = 269378154809
547*673*829*941 = 287174943659
479*823*853*859 = 288853439759
541*797*823*829 = 294177838259
439*811*907*929 = 299991103487
613*631*859*947 = 314653796819
457*811*863*997 = 318891547697

The next 4-fang PVN is the smallest with 4-digit fangs: 2711*5023*8101*9067 = 1000218639712751

The smallest 5-fang PVN is:

307*607*719*853*881 = 100688737751983

Smallest 6-fang PVN:

503*641*653*701*727*941 = 100967417475216533

***

Question 4 was solved by J. K. Andersen:

This turned out to be far easier than expected with the right algorithm. I could easily have found a titanic solution. It only took a couple of minutes running to find the 500-digit PVN:

(55*10^248+229)*(74*10^248+8961) = 4070*10^496+509801*10^248+2052069 Lots of 0's in both fangs greatly increases the probability of a vampire number, because the 0's are mostly repeated in the product and few remaining digits must match. I first used the Miracl big integer library to compute a set of 966 250-digit probable primes on the form c*10^248+d with 40<=c<100 and 0<d<10000. For each combination of two such primes:

(c1*10^248+d1)*(c2*10^248+d2) = (c1*c2)*10^496+(c1*d2+c2*d1)*10^248+(d1*d2)

It is not necessary to compute the full product since this is a vampire number if the non-zero digits in (c1,d1,c2,d2) are the same (but permuted) as in (c1*c2,c1*d2+c2*d1,d1*d2). I checked that with a C program using simple 32-bit variables and it occurred exactly once, giving the above solution. The two prp fangs were then proven prime with Primo.

***

I wrote to Andersen "Then you should try the Titanic target, don't you think so?". What he got is a superb result: "several formulas to generate infinitely many squared vampire numbers... one of them has a chance of making a squared PVN"

I tried with 2 1000-digit fangs, i.e.. a 2000-digit PVN, but I had bad luck. It is easier if the requested size is not fixed. I found several formulas to generate infinitely many squared vampire numbers. Only one of them has a chance of making a squared PVN: (351995*10^n+283497)^2 = 123900480025*10^(2n)+199579053030*10^n+80370549009, for n>11

Example with n=18 (not prime):

(351995000000000000283497)^2 = 123900480025000000199579053030000000080370549009

The fang is divisible by 11 for all even n. According to Primeform/GW it is a probable prime in several bases for n = 409, 1629, 1893, 4335. This gives 4 (probable) PVN:

(351995*10^409+283497)^2
(351995*10^1629+283497)^2
(351995*10^1893+283497)^2
(351995*10^4335+283497)^2

The prime fang has n+6 digits and the PVN 2n+12 digits.

The 415-digit prime has been proved with Primo. The next 2 primes could be proved in around 1 day but I omit it. The largest prime has 4341 digits and the PVN 8682 digits. It could take months with Primo. I cannot find a sequence with easily provable primes. I guess there are infinitely many primes and corresponding PVN in the sequence. I have only tested to n=7800 so far but I will let Primeform run longer and hope for a gigantic prp.

...

(update) 351995*10^8217+283497 is a probable prime with a 16446-digit PVN. The search has passed n=10000

...

(last update: 30/10/2002):

Update:

I used Primo to prove 351995*10^n+283497 is prime for n = 409, 1629, 1893. I have prp tested to n=21000. It is prp for n = 4335, 8217, 12173.

I found a new improved formula for squared PVN:

f(n) = 596825*10^n+3.
f(n)^2 = 356200080625*10^(2n)+3580950*10^n+9
This is a vampire number for all n>6.

f(n) seems richer in primes. 7 divides f(n) for every 6 n, 17 for every 16 n, 19 for every 18 n, but this is almost the expected.

f(n) is prime for n = 1, 3, 6, but makes no PVN here.

f(n) is prp for n = 16, 103, 260, 280, 361, 1297, 1771, 2240, 3338, 3354. This makes 10 (probable) PVN, enough for question 1.

f(n) has also been prp tested to n=21000.

Primo has proved the primes for n = 16, 103, 260, 280, 361, 1297. The two largest would take around 2 weeks each to prove. It is feasible but I certainly don't want to do it. I don't know whether there is a faster method when only 3 is added to the factored part of f(n).

According to my search, there are only these 2 PVN-capable formulas of the form (c*10^n+d)^2, with c and d both below 700000.

***

One more interesting update to question 4, from J. K. Andersen (1/11/02):

I searched and found a formula with easily provable primes:

(94892254795*10^n+1)^2 = 9004540020079200492025*10^(2n) + 189784509590*10^n+1.

This is a PVN for n = 41, 65, 75, 257, 633, 730, 4755, 4780, 16868. The largest PVN has 33758 digits. The primes were found and proven with PrimeForm/GW. Now that I have a provable form, I will let it run longer.

The 20/11/2002 he wrote this:

My patience has been rewarded. Output from PrimeForm/GW: "PFGW Version 20020515.Win_Dev (Beta software, 'caveat utilitor')

Primality testing 94892254795*10^45418+1 [N-1, Brillhart-Lehmer-Selfridge] Running N-1 test using base 3 Calling Brillhart-Lehmer-Selfridge with factored part 69.88% 94892254795*10^45418+1 is prime! (665.346000 seconds)"

The prime has 45429 digits and I have just submitted it to the 5000 largest known primes with the comment "Square is vampire number" (which may be removed). It gives a PVN with 90858 digits: (94892254795*10^45418+1)^2 = 9004540020079200492025*10^90836+189784509590*10^45418+1

***

Walter Schneider wrote (24/11/2002):

two remarks to the Vampire Number puzzle:

Question 2: I have searched PVN's for k=8 and k=10 up to 11 digit fangs. No solution was found. Therefore a solution must have at least 12 digit fangs. I believe there are infinitely many solutions.

Question 3: The smallest k-fang PVN with k distinct fangs for k=7,...,10 are: k = 7: 101.579.148.179.968.321.559 = 523 * 541 * 571 * 809 * 811 * 967 * 991
k = 8: 100.788.927.299.477.317.689.377 = 487 * 607 * 701 * 739 * 821 * 823 * 977 * 997
k = 9: 104.872.975.389.659.659.789.317.349 = 353 * 647 * 821 * 853 * 859 * 907 * 919 * 947 * 967
k = 10: 100.389.828.853.193.687.767.547.999.987 = 503 * 691 * 761 * 809 * 829 * 839 * 857 * 887 * 937 * 947

***

J. C. Rosa  found (May 2003) the following results for PVN's:

They are the two smallest solutions of the equality:

V=F*R where V is a PVN , R is the reverse of F.

136607905159255237=193625507*705526391
12701236096515714439=1317520469*9640257131

Others are:

17582650323680176699=1806562379*9732656081 25550623091507607931=3515009627*7269005153 69812914325722548763=7254183269*9623814527

Now he is looking for one of these solutions but with F palprime.

And I add the following additional targets:

a) get a titanic V?

b) get a titanic F?

***

More interesting soutions came from J. C. Rosa (May 2003)

The smallest solutions of the equation :
   PVN=Palprime1*Palprime2 , are :
 
113489296116324277=143181341*792626297
 
135440880733351399=145030541*933878339
 
680670321229667983=706222607*963818369

***

J. K. Andersen added (Sept, 07):

A new record with my old formula:
PrimeForm/GW found that 94892254795*10^103294+1 is prime, so
(94892254795*10^103294+1)^2 is a 206610-digit prime vampire number.
Many exponents between 45418 and 103294 have not been tested.
 

***

 

 

 



Records   |  Conjectures  |  Problems  |  Puzzles