1
$\begingroup$

Let $k\ge 3$ be an intger. The object is to find the smallest number $n$ above $10^k$ which is the product of two distinct primes, each greater than $11$ and containing at most $2$ distinct decimal digits. The numbers for $3$ upto $11$ are :

? for(s=3,11,n=10^s;gef=0;while(gef==0,n=n+1;w=factor(n);if(Set(component(w,2))=
=[1],if(length(component(w,1))==2,if(component(w,1)[1]>11,if(length(Set(digits(c
omponent(w,1)[1])))<=2,if(length(Set(digits(component(w,1)[2])))<=2,gef=1))))));
print(s,"    ",n,"  ",w))
3    1003  [17, 1; 59, 1]
4    10019  [43, 1; 233, 1]
5    100091  [101, 1; 991, 1]
6    1002013  [31, 1; 32323, 1]
7    10002373  [449, 1; 22277, 1]
8    100005887  [8999, 1; 11113, 1]
9    1000047757  [11113, 1; 89989, 1]
10    10000252373  [449, 1; 22272277, 1]
11    100004653457  [11113, 1; 8998889, 1]

Which numbers come next ? In particular, what is the number for $k=12$ ?

$\endgroup$
  • $\begingroup$ What do you mean by at most two distinct decimal digits. $\endgroup$ – Don Thousand Nov 7 '18 at 16:32
  • $\begingroup$ The primes must contain of at most $2$ distinct digits, so $1229$ for example would not be allowed because $1,2,9$ make $3$ distinct digits. $\endgroup$ – Peter Nov 7 '18 at 16:34
  • $\begingroup$ I feel like this would be a more valuable question if there were some motivation as to why we'd expect there to be a pattern. Did you compute these via brute force? $\endgroup$ – Don Thousand Nov 7 '18 at 16:36
  • $\begingroup$ @RushabhMehta I do not expect a pattern, I am just curious how this sequence goes on. Yes, I used brute force. $\endgroup$ – Peter Nov 7 '18 at 16:42
  • $\begingroup$ I'm not convinced that there's a better way to find these values other than brute force, or educated guess brute force, but I'll see if smarter minds than me can figure something out. $\endgroup$ – Don Thousand Nov 7 '18 at 16:51
2
$\begingroup$

Here's the output from a program I wrote. It confirms the values for $3\le k\le11$ and gives values for $12\le k\le20$.

 3 1003 [17, 59]
 4 10019 [43, 233]
 5 100091 [101, 991]
 6 1002013 [31, 32323]
 7 10002373 [449, 22277]
 8 100005887 [8999, 11113]
 9 1000047757 [11113, 89989]
10 10000252373 [449, 22272277]
11 100004653457 [11113, 8998889]
12 1000010666663 [333337, 2999999]
13 10000079888899 [989999, 10101101]
14 100000008888889 [99989, 1000110101]
15 1000000518888883 [11111117, 89999999]
16 10000000058888887 [89999999, 111111113]
17 100000005178888819 [89999999, 1111111181]
18 1000000000099987889 [99999989, 10000001101]
19 10000000000097987989 [99998999, 100001001011]
20 100000000088787877679 [9999889, 10000111010111]

Here's my approach. It's brute force but works by restricting the range of primes it needs to test. Wherever it refers to a 'valid prime' it means a prime with $1$ or $2$ distinct decimal digits.

I found this was quicker than testing successive $n>10^k$.

For each k
   Find p,q, being the first two valid primes above sqrt(10^k)
   Set N, an upper bound, as p*q

   For all valid primes p1, with 11<p1<=sqrt(N)
      Find p2 being the smallest prime such that p2>10^k/p1
      Increase p2 through all primes until either p2 is a valid prime or p1*p2>N
         If p2 is a valid prime and p1*p2<N
             Set N=p1*p2
             Store p1,p2 as best[p1,p2]

   Output k,N,best[p1,p2]

(Edit: Added results for $k=19$ and $k=20$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.