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$
5
  • $\begingroup$ What do you mean by at most two distinct decimal digits. $\endgroup$
    – Rushabh Mehta
    Commented Nov 7, 2018 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
    Commented Nov 7, 2018 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$
    – Rushabh Mehta
    Commented Nov 7, 2018 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
    Commented Nov 7, 2018 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$
    – Rushabh Mehta
    Commented Nov 7, 2018 at 16:51

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .