# Which is the smallest semiprime above $10^k$ with the desired property?

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$$ ?

• What do you mean by at most two distinct decimal digits. – Don Thousand Nov 7 '18 at 16:32
• 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. – Peter Nov 7 '18 at 16:34
• 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? – Don Thousand Nov 7 '18 at 16:36
• @RushabhMehta I do not expect a pattern, I am just curious how this sequence goes on. Yes, I used brute force. – Peter Nov 7 '18 at 16:42
• 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. – Don Thousand Nov 7 '18 at 16:51

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$$.)