Problems & Puzzles:
Puzzles
Puzzle 231.
kPersistent primes
A kpersistent number n, is such that
all of the following numbers: n, 2.n,
3.n, ..., k.n
contains all the digits from 0 to 9 (see
1)
Eric Weisstein shows
526315789473684210
as an example of a
18persistent number. In the same article is said that:
“There
exists at least one kpersistent number for each
positive integer
k.”
Here we will ask for kpersistent
primes.
As a matter of fact I have calculated
the earliest of these for a few k values:
k 
p=prime 
Author 
2 
10123457689 
CR 
3 
10512867493 
CR 
4 
11267085493 
CR 
5 
? 
? 
6 
? 
? 
7 
? 
? 
8 
? 
? 
9 
? 
? 
10 
? 
? 
Questions:
1. Can you
complete the table above?
2.
Is it true the
following statement?
“There exists at
least one kpersistent prime
for each positive integer k.”
3. Do you devise a
regular smartapproach
in order to find
a kpersistent
prime
for a given k value?
Solution:
Adam Stinchcombe, Jim Fougeron,
Luke Pebody and Gilles Blanchette sent contributions to this
puzzle.
Adam Stinchcombe wrote for the
questions 2 & 3:
Certainly, the k in kpersistent
primes runs to infinity, that is, for arbitrarily large numbers K there
is some p which is kpersistent with k>=K. If you take p large enough,
say 30 or 100 digits or thereabouts, it is going to be almost impossible
for p and its multiples not to be kpersistent for relatively large k
values. E.g., I used Maple to get a random 12 digit number, cubed this
to get a 36 digit number, took the next prime and then tested the
kpersistence and quickly found 416420764462383215203462851467280961 to
be 43persistent.
Note in my claim, that k>=K. In
fact, it might be hard to find some p value that is exactly Kpersistent
but NOT (K+1)persistent for large K.
The search then becomes what is the
smallest p value that gives a given k.
***
Jim Fougeron obtained the next
entries for the Table, question 1:
5: 48657940213
6: 175647382901
7: 6440261849537
8: 6435409832617 (the only length 8 found
so far).
Here are all of the length 7's I have found so far:
6440261849537
8189804352617
8399476581203
8545801642739
8600567921483
8901529806437
8936758491203
10180854731629
10919651402873
10973564701829
10990182935647
11727649358021
My method is very brute force.
1. generated a file of permutations of 0123456789.
This file was trimmed to only store values if the last digit is 1,3,7 or 9
1a. All of these are divisible by 3, so there can be
no 10 digit primes. (as was shown by the minimal 2persistant being 11
digits)
2. read this file, and append a 1, 2, 3, ... 9 to
each line. Slightly Trial factor these to 53, and output what was not
factored out.
3. Run PFGW on this.
4. The PFGW.LOG results are the primes to start from
(only PRP here, but I only cared about proving prime once I found deep
enough kPersistent.
5. Rerun these candidates, multiplied by 2 using
pfgw d od l (only outputs decimal expansion, and logs the results)
6. I created a "finder" program which found the
resultant numbers which had all 10 needed digits. This was run on the
pfgw.out file.
7. goto Step 5 with the resultant, but multiply by
3, 4, 5, 6 (no 6's found yet).
This is certainly not a very good way to proceed,
but it does work. It could be extended, by changing step 2 to append 10,
11, 12, 13, ... 99 then 100, 101, 102, ... 999 etc, until the required
kpersistent prime(s) are found.
***
Luke Pebody sent the following strategy, for
the question 3:
Take an npersistent number k.
Then find a prime of the form k*l (here * is
concatenation) where l is a sequence of tdigits (possibly starting with a
0) such that nl<10^t. Then k*l=10^tk+l, and hence for 1<=i<=n,
i(k*l)=10^t(ik)+il. Since il<10^t, all the digits of ik are digits of
i(k*l), and hence k*l is npersistent.
***
Gilles Blanchette wrote
for the question 2 & 3:
Question #2 and #3
Here is an algorithm that generate a kpersistent
prime for a positive integer up to k
// Start with a pandigital prime number
// p = 10123456789
//
// [1]
// let m = 2
//
// [2]
// if m*p is pandigital
// m = m + 1
// elseif
// let c = the catenation of missing digit
// let t = 0
// while ( m do not divide c.t  ((c.t)/m).p is not prime  ((c.t)/m).p
is not pandigital ) let t = t + 1
// let p = ((c.t)/m).p
// goto [1]
// endif
//
// if ( m <= k ) goto [2]
//
// p is a kpersistent prime
Note : a.b is catenation of number a and b.
Note : The while (...) t = t + 1 will not loop indefinitely, especially
because there is infinite prime number ending with same digit as p.
Here is some kilopersistent prime generated by an
implementation slightly different from the algorithm.
k = 1485 >
2902511412532342619044701292813017107352161725041764195705797485949876543201
k = 1747 >
5022902511412532342619044701292813017107352161725041764195705797485949876543201
k = 1302 >
253291602612432511430879554120442275104130070909568930570130485949876543021
k = 1487 >
71841996227831827538516486910161635153401069558561312094152971023456789
k = 1485 >
50620311533350132357510055408221582220301073013852065792275819641203456789
k = 1084 >
9613412011013356332915450663013770120213025163520113698109062581941230456789
k = 5048 >
4014130683952091511536094003195451109764411727213402060919322152601630451234056789
k = 1213 >
189056174111492144775403011813423210204414116499130026049641234506789
k = 1550 >
872189056174111492144775403011813423210204414116499130026049641234506789
k = 1636 >
3979103316515292419613260110588511015017025034010572091041918064151234560789
k = 1521 >
11873318548192835580355011768120262812301538441356115854152972345678901
k = 1060 >
465213528414751273415776760141460163519650224935425290599819374567890123
k = 1646 >
4800121226143752663735138701551730222201044321760810381964258901234567
***
