Problems & Puzzles:
Puzzles
Puzzle 199.
The
PrimeVampire 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 2fangs
VN is: 1260 = 21 x 60
Extending the idea to more than two fangs:
 The smallest example of a 3fangs
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 2fangs
PVN is: 117067 =
167x701
 The least example of a squared PVN is:
2459319153459529 = (49591523)^{2}
Questions
 Find
10 more squared PVN
 Find the least PVN= (fang)^k, for
6=>k=>3
 Find the least
PVN with k distinct fangs, for k = 3 & 4
 Find a
semititanic
(500 digits) PVN
_____
Vampire Numbers, Web References:
Eric Weisstein,
Walter
Schneider,
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 followup 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 3digit 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 4fang PVN is the smallest with 4digit
fangs: 2711*5023*8101*9067 = 1000218639712751
The smallest 5fang PVN is:
307*607*719*853*881 = 100688737751983
Smallest 6fang 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 500digit 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 250digit 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 nonzero 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 32bit 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 1000digit fangs, i.e.. a 2000digit
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 415digit 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 16446digit 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 PVNcapable 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 [N1, BrillhartLehmerSelfridge]
Running N1 test using base 3 Calling BrillhartLehmerSelfridge 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 kfang 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 206610digit prime vampire number.
Many exponents between 45418 and 103294 have not been tested.
***
