Hard recreational math problems

[swishzzz]

Are problems like these remotely solvable using known number theoretic methods?

1. Prove/disprove that there exists a square whose decimal representation contains only 0's and 1's and is not of the form 100^n for some integer n. Modulo chasing doesn't really help here, it's possible to construct a square that ends in x1001 where x is any string of 0's and 1's. I don't know where one would even begin with this problem.

2. Prove/disprove there are infinitely many primes whose decimal representation does not contain the digit 9. For large n there are roughly n/log(n) primes below it and roughly 9^(log(n)/log(10)) = 9^(log(n)/log(9) * log(9)/log(10)) = n^0.954 numbers that do not contain the digit 9. If we randomly picked n/log(n) numbers from 1..n for say set A and n^0.954 numbers from 1..n for set B, the probability of A and B having no common intersection is something like (1-1/log(n)) ^ (n^0.954) ~ exp(-n^0.954/log(n)) for large n assuming n^0.954 << n/log(n) which is pretty damn close to zero, but of course this isn't really a proof. However this also seems much weaker than one of Landau's problems which states that are infinitely many primes of the form n^2+1 so this one seems like it should be "easier".

[Dr Sardonicus]

Originally Posted by swishzzz

Are problems like these remotely solvable using known number theoretic methods?
<snip>
2. Prove/disprove there are infinitely many primes whose decimal representation does not contain the digit 9. For large n there are roughly n/log(n) primes below it and roughly 9^(log(n)/log(10)) = 9^(log(n)/log(9) * log(9)/log(10)) = n^0.954 numbers that do not contain the digit 9. If we randomly picked n/log(n) numbers from 1..n for say set A and n^0.954 numbers from 1..n for set B, the probability of A and B having no common intersection is something like (1-1/log(n)) ^ (n^0.954) ~ exp(-n^0.954/log(n)) for large n assuming n^0.954 << n/log(n) which is pretty damn close to zero, but of course this isn't really a proof. However this also seems much weaker than one of Landau's problems which states that are infinitely many primes of the form n^2+1 so this one seems like it should be "easier".

I think this one is known... (Google Google) Here we go! Primes with restricted digits. PDF here.

So it is proven, but don't ask me to explain the proof...

Still thinking about first problem...

[ATH]

2. was proven by James Maynard: https://arxiv.org/abs/1604.01041

Yes, there are infinitely many primes without 9 or 7 or any single digit removed.

[Ethan (EO)]

Originally Posted by ATH

2. was proven by James Maynard: https://arxiv.org/abs/1604.01041

Yes, there are infinitely many primes without 9 or 7 or any single digit removed.

Is anything known about more than one single digit removed? What's the largest set of digits base-10 such that there at least (choose your own bound here) primes containing none of those digits?

[Dr Sardonicus]

I've hit an impasse with problem 1 (squares whose only decimal digits are 1 and 0).

Apparently unsolved. Best I could do was OEIS A016070, Numbers n such that n^2 contains exactly 2 different digits, excluding 10^m, 2*10^m, 3*10^m.

Gives 21 terms, "No other terms below 3.16*10^20" Sequence thought to be finite.

[Batalov]

Originally Posted by Ethan (EO)

Is anything known about more than one single digit removed? What's the largest set of digits base-10 such that there at least (choose your own bound here) primes containing none of those digits?

There is no proof, but you could most likely withdraw nine digits, -- all except "1".
There is likely an infinity of primes that are decimal repeated units.

[swishzzz]

Originally Posted by Ethan (EO)

Is anything known about more than one single digit removed? What's the largest set of digits base-10 such that there at least (choose your own bound here) primes containing none of those digits?

According to Theorem 1.2 in the paper, given a base-q, an integer s <= q^0.2875, and any base-q digits 0 <= a_1, ..., a_s <= q-1, there are infinitely many primes such that the base-q representation do not contain any of a_1, ..., a_s. 10^0.2875 = 1.9386, so the proof here doesn't quite work for 2 or more (decimal) digits.

[Dr Sardonicus]

Originally Posted by swishzzz

Are problems like these remotely solvable using known number theoretic methods?

1. Prove/disprove that there exists a square whose decimal representation contains only 0's and 1's and is not of the form 100^n for some integer n. Modulo chasing doesn't really help here, it's possible to construct a square that ends in x1001 where x is any string of 0's and 1's. I don't know where one would even begin with this problem.
<snip>

I decided to do some brute-force checking. If there were a square whose decimal digits are all 1's and 0's, and isn't a power of 100, the smallest one would end in the digit 1. All odd squares are congruent to 1 (mod 8) so for any candidates > 100, the last 3 digits have to be 001.

Also, squares between 100^k and 10*100^k are >= (10^k + 1)^2 = 100^k + 2*10^k + 1 so have a 1 in the 10^(k+1) position or higher.

It occurred to me that the number of squares between 10^k and (10^(k+1) - 1)/9 is of order 10^(k/2) with a modest "big-O constant," while the number of candidate numbers composed of 1's and 0's is "only" of order 2^k, with a modest "big-O" constant. The number of candidates still grows exponentially with the number of digits, but 2 < sqrt(10).

The fact that the remainder square%9 can only be 0, 1, 4, or 7 also allows a reduction in the number of candidates by a constant factor. I'll take what I can get.

I incorporated these ideas in some "proof of concept" bare-bones Pari-GP scripts. First, I merely checked that they produced the desired numbers. I give samples for MSD even and odd powers of 10. I didn't get as far as automating this. I looked at factorizations to see if anything interesting appeared.

? forstep(n=32+1,63,8,v=binary(n);s=sum(i=1,#v,v[i]);r=s%9;if(r==0||r==1||r==4||r==7,c=sum(i=1,#v,10^(#v-i)*v[i]);print(c" "factor(c))))
111001 [11, 1; 10091, 1]

? forstep(n=64+16+1,127,8,v=binary(n);s=sum(i=1,#v,v[i]);r=s%9;if(r==0||r==1||r==4||r==7,c=sum(i=1,#v,10^(#v-i)*v[i]);print(c" "factor(c))))
1011001 Mat([1011001, 1])
1101001 [11, 1; 101, 1; 991, 1]
1110001 [151, 1; 7351, 1]

I decided to press on, one digit at a time, until I at least got a number with a square factor greater than 1.

 ? forstep(n=2048+1,4095,8,v=binary(n);s=sum(i=1,#v,v[i]);r=s%9;if(r==0||r==1||r==4||r==7,c=sum(i=1,#v,10^(#v-i)*v[i]);print(c" "factor(c))))
<snip>
100010100001 [7, 2; 233, 1; 1409, 1; 6217, 1]
<snip>
101111111001 [3, 6; 138698369, 1]
<snip>

If you merely want to check the numbers for squareness, the thing to do is ditch the time-consuming factorization, and use issquare(), with a break() to terminate the program if you get lucky.

I doubt you'll get lucky with any number of digits for which the above code would run in a reasonable length of time.

IMO any significant progress on this problem would require other ideas.

[sweety439]

It is conjectured that, in every base b, for a given form x{d}y (i.e. xddd...dddy) (where d is a digit in base b, x and y are strings (the strings can be empty) in base b) such that there is no obvious reason why there can’t be a prime (or can be only prime for very small numbers, e.g. 111 (decimal 73) is the only prime of the form {1} in base 8, and D (decimal 13) is the only prime of the form {C}D in base 16) of the form x{d}y, then there are infinitely many primes of the form x{d}y, see page 12 of the article https://cs.uwaterloo.ca/~cbright/reports/mepn.pdf

Since x{d}y (for fixed digit d and strings x,y (the strings can be empty)) in base b is (k*b^n+c)/gcd(k+c, b-1) for some fixed k>=1, c<>0, and with gcd(k, c) = 1, gcd(b, c) = 1, and this is conjectured that for any given integer triple (k,b,c) such that k>=1, b>=2, c != 0, gcd(k, c) = 1, gcd(b, c) = 1 and there is no obvious reason why there can’t be a prime (or can be only prime for very small n, e.g. (4,16,1), (27,8,1), (1,4,-1), (1,16,-1), (1,27,-1), (1,36,-1), (1,128,-1), etc.) of the form (k*b^n+c)/gcd(k+c, b-1), then there are infinitely many integers n>=1 such that (k*b^n+c)/gcd(k+c, b-1) is prime, the obvious reason may be "full numeric covering set", "full algebraic covering set", or "partial numeric, partial algebraic covering set", thus, it is conjectured that, in every base b, for a given form x{d}y such that there is no obvious reason why there can’t be a prime (or can be only prime for very small numbers) of the form x{d}y, then there are infinitely many primes of the form x{d}y.

Examples of some (k,b,c) triple (k>=1, b>=2, c != 0, gcd(k, c) = 1, gcd(b, c) = 1) such that we can show that there is no primes of the form (k*b^n+c)/gcd(k+c, b-1) with n>=1, by "full numeric covering set", "full algebraic covering set", or "partial numeric, partial algebraic covering set":

* (k,b,c) = (78557,2,1), in which all numbers are divisible by at least one of 3, 5, 7, 13, 19, 37, 73

* (k,b,c) = (271129,2,1), in which all numbers are divisible by at least one of 3, 5, 7, 13, 17, 241

* (k,b,c) = (11047,3,1), in which all numbers are divisible by at least one of 2, 5, 7, 13, 73

* (k,b,c) = (419,4,1), in which all numbers are divisible by at least one of 3, 5, 7, 13

* (k,b,c) = (659,4,1), in which all numbers are divisible by at least one of 3, 5, 13, 17, 241

* (k,b,c) = (794,4,1), in which all numbers are divisible by at least one of 3, 5, 7, 13

* (k,b,c) = (7,5,1), in which all numbers are divisible by either 2 or 3

* (k,b,c) = (11,5,1), in which all numbers are divisible by either 2 or 3

* (k,b,c) = (174308,6,1), in which all numbers are divisible by at least one of 7, 13, 31, 37, 97

* (k,b,c) = (47,8,1), in which all numbers are divisible by at least one of 3, 5, 13

* (k,b,c) = (989,10,1), in which all numbers are divisible by at least one of 3, 7, 11, 13

* (k,b,c) = (5,11,1), in which all numbers are divisible by either 2 or 3

* (k,b,c) = (7,11,1), in which all numbers are divisible by either 2 or 3

* (k,b,c) = (521,12,1), in which all numbers are divisible by at least one of 5, 13, 29

* (k,b,c) = (4,14,1), in which all numbers are divisible by either 3 or 5

* (k,b,c) = (509203,2,-1), in which all numbers are divisible by at least one of 3, 5, 7, 13, 17, 241

* (k,b,c) = (334,10,-1), in which all numbers are divisible by at least one of 3, 7, 13, 37

* (k,b,c) = (1585,10,-1), in which all numbers are divisible by at least one of 3, 7, 11, 13

* (k,b,c) = (376,12,-1), in which all numbers are divisible by at least one of 5, 13, 29

* (k,b,c) = (919,4,-1), in which all numbers are divisible by at least one of 3, 5, 7, 13

* (k,b,c) = (13,5,-1), in which all numbers are divisible by either 2 or 3

* (k,b,c) = (17,5,-1), in which all numbers are divisible by either 2 or 3

* (k,b,c) = (14,8,-1), in which all numbers are divisible by at least one of 3, 5, 13

* (k,b,c) = (116,8,-1), in which all numbers are divisible by at least one of 3, 5, 13

* (k,b,c) = (148,8,-1), in which all numbers are divisible by at least one of 3, 5, 13

* (k,b,c) = (5,11,-1), in which all numbers are divisible by either 2 or 3

* (k,b,c) = (7,11,-1), in which all numbers are divisible by either 2 or 3

* (k,b,c) = (1,4,-1), in which all numbers factored as difference of squares

* (k,b,c) = (9,4,-1), in which all numbers factored as difference of squares

* (k,b,c) = (1,9,-1), in which all numbers factored as difference of squares

* (k,b,c) = (4,9,-1), in which all numbers factored as difference of squares

* (k,b,c) = (16,9,-1), in which all numbers factored as difference of squares

* (k,b,c) = (1,16,-1), in which all numbers factored as difference of squares

* (k,b,c) = (4,16,-1), in which all numbers factored as difference of squares

* (k,b,c) = (9,16,-1), in which all numbers factored as difference of squares

* (k,b,c) = (25,16,-1), in which all numbers factored as difference of squares

* (k,b,c) = (36,16,-1), in which all numbers factored as difference of squares

* (k,b,c) = (1,4,-9), in which all numbers factored as difference of squares

* (k,b,c) = (1,4,-25), in which all numbers factored as difference of squares

* (k,b,c) = (1,9,-4), in which all numbers factored as difference of squares

* (k,b,c) = (1,9,-16), in which all numbers factored as difference of squares

* (k,b,c) = (1,4,-25), in which all numbers factored as difference of squares

* (k,b,c) = (1,8,1), in which all numbers factored as sum of cubes

* (k,b,c) = (27,8,1), in which all numbers factored as sum of cubes

* (k,b,c) = (125,8,1), in which all numbers factored as sum of cubes

* (k,b,c) = (343,8,1), in which all numbers factored as sum of cubes

* (k,b,c) = (729,8,1), in which all numbers factored as sum of cubes

* (k,b,c) = (1,8,27), in which all numbers factored as sum of cubes

* (k,b,c) = (1,27,1), in which all numbers factored as sum of cubes

* (k,b,c) = (8,27,1), in which all numbers factored as sum of cubes

* (k,b,c) = (1,27,8), in which all numbers factored as sum of cubes

* (k,b,c) = (1,8,-1), in which all numbers factored as difference of cubes

* (k,b,c) = (27,8,-1), in which all numbers factored as difference of cubes

* (k,b,c) = (1,8,-27), in which all numbers factored as difference of cubes

* (k,b,c) = (125,8,-1), in which all numbers factored as difference of cubes

* (k,b,c) = (1,27,-1), in which all numbers factored as difference of cubes

* (k,b,c) = (8,27,-1), in which all numbers factored as difference of cubes

* (k,b,c) = (1,27,-8), in which all numbers factored as difference of cubes

* (k,b,c) = (1,32,1), in which all numbers factored as sum of 5th powers

* (k,b,c) = (1,32,-1), in which all numbers factored as difference of 5th powers

* (k,b,c) = (4,16,1), in which all numbers factored as x^4+4*y^4

* (k,b,c) = (324,16,1), in which all numbers factored as x^4+4*y^4

* (k,b,c) = (2500,16,1), in which all numbers factored as x^4+4*y^4

* (k,b,c) = (4,81,1), in which all numbers factored as x^4+4*y^4

* (k,b,c) = (4,256,1), in which all numbers factored as x^4+4*y^4

* (k,b,c) = (4,625,1), in which all numbers factored as x^4+4*y^4

* (k,b,c) = (64,81,1), in which all numbers factored as x^4+4*y^4

* (k,b,c) = (64,256,1), in which all numbers factored as x^4+4*y^4

* (k,b,c) = (64,625,1), in which all numbers factored as x^4+4*y^4

* (k,b,c) = (324,256,1), in which all numbers factored as x^4+4*y^4

* (k,b,c) = (324,625,1), in which all numbers factored as x^4+4*y^4

* (k,b,c) = (25,12,-1), in which even n factored as difference of squares and odd n is divisible by 13

* (k,b,c) = (64,12,-1), in which even n factored as difference of squares and odd n is divisible by 13

* (k,b,c) = (4,19,-1), in which even n factored as difference of squares and odd n is divisible by 5

* (k,b,c) = (9,14,-1), in which even n factored as difference of squares and odd n is divisible by 5

* (k,b,c) = (4,24,-1), in which even n factored as difference of squares and odd n is divisible by 5

* (k,b,c) = (9,24,-1), in which even n factored as difference of squares and odd n is divisible by 13

* (k,b,c) = (4,39,-1), in which even n factored as difference of squares and odd n is divisible by 5

* (k,b,c) = (9,34,-1), in which even n factored as difference of squares and odd n is divisible by 5

* (k,b,c) = (81,17,-1), in which even n factored as difference of squares and odd n is divisible by 2

* (k,b,c) = (144,28,-1), in which even n factored as difference of squares and odd n is divisible by 29

* (k,b,c) = (289,28,-1), in which even n factored as difference of squares and odd n is divisible by 29

* (k,b,c) = (16,33,-1), in which even n factored as difference of squares and odd n is divisible by 17

* (k,b,c) = (225,33,-1), in which even n factored as difference of squares and odd n is divisible by 2

* (k,b,c) = (289,33,-1), in which even n factored as difference of squares and odd n is divisible by 2

* (k,b,c) = (6,24,-1), in which odd n factored as difference of squares and even n is divisible by 5

* (k,b,c) = (27,12,-1), in which odd n factored as difference of squares and even n is divisible by 13

* (k,b,c) = (6,54,-1), in which odd n factored as difference of squares and even n is divisible by 5

* (k,b,c) = (76,19,-1), in which odd n factored as difference of squares and even n is divisible by 5

* (k,b,c) = (126,14,-1), in which odd n factored as difference of squares and even n is divisible by 5

* (k,b,c) = (300,12,-1), in which odd n factored as difference of squares and even n is divisible by 13

* (k,b,c) = (16,12,-49), in which even n factored as difference of squares and odd n is divisible by 13

* (k,b,c) = (441,12,-1), in which even n factored as difference of squares and odd n is divisible by 13

* (k,b,c) = (1156,12,-1), in which even n factored as difference of squares and odd n is divisible by 13

* (k,b,c) = (25,17,-9), in which even n factored as difference of squares and odd n is divisible by 2

* (k,b,c) = (1369,30,-1), in which even n factored as difference of squares and odd n is divisible by at least one of 7, 13, 19

* (k,b,c) = (400,88,-1), in which even n factored as difference of squares and odd n is divisible by at least one of 3, 7, 13

* (k,b,c) = (324,95,-1), in which even n factored as difference of squares and odd n is divisible by at least one of 7, 13, 229

* (k,b,c) = (3600,270,-1), in which even n factored as difference of squares and odd n is divisible by at least one of 7, 13, 37

* (k,b,c) = (93025,498,-1), in which even n factored as difference of squares and odd n is divisible by at least one of 13, 67, 241

* (k,b,c) = (61009,540,-1), in which even n factored as difference of squares and odd n is divisible by at least one of either 17 or 1009

* (k,b,c) = (343,10,-1), in which n divisible by 3 factored as difference of cubes and other n divisible by either 3 or 37

* (k,b,c) = (3511808,63,1), in which n divisible by 3 factored as sum of cubes and other n divisible by either 37 or 109

* (k,b,c) = (27000000,63,1), in which n divisible by 3 factored as sum of cubes and other n divisible by either 37 or 109

* (k,b,c) = (64,957,-1), in which n divisible by 3 factored as sum of cubes and other n divisible by either 19 or 73

* (k,b,c) = (2500,13,1), in which n divisible by 4 factored as x^4+4*y^4 and other n divisible by either 7 or 17

* (k,b,c) = (2500,55,1), in which n divisible by 4 factored as x^4+4*y^4 and other n divisible by either 7 or 17

* (k,b,c) = (16,200,1), in which n == 2 mod 4 factored as x^4+4*y^4 and other n divisible by either 3 or 17

* (k,b,c) = (64,936,-1), in which even n factored as difference of squares and n divisible by 3 factored as difference of cubes and other n divisible by either 37 or 109

* (k,b,c) = (8,128,1), in which the form equals 2^(7*n+3)+1 but 7*n+3 cannot be power of 2

* (k,b,c) = (32,128,1), in which the form equals 2^(7*n+5)+1 but 7*n+5 cannot be power of 2

* (k,b,c) = (64,128,1), in which the form equals 2^(7*n+6)+1 but 7*n+6 cannot be power of 2

* (k,b,c) = (8,131072,1), in which the form equals 2^(17*n+3)+1 but 17*n+3 cannot be power of 2

* (k,b,c) = (32,131072,1), in which the form equals 2^(17*n+5)+1 but 17*n+5 cannot be power of 2

* (k,b,c) = (128,131072,1), in which the form equals 2^(17*n+7)+1 but 17*n+7 cannot be power of 2

* (k,b,c) = (27,2187,1), in which the form equals (3^(7*n+3)+1)/2 but 7*n+3 cannot be power of 2

* (k,b,c) = (243,2187,1), in which the form equals (3^(7*n+5)+1)/2 but 7*n+5 cannot be power of 2

[sweety439]

Originally Posted by swishzzz

Are problems like these remotely solvable using known number theoretic methods?

1. Prove/disprove that there exists a square whose decimal representation contains only 0's and 1's and is not of the form 100^n for some integer n. Modulo chasing doesn't really help here, it's possible to construct a square that ends in x1001 where x is any string of 0's and 1's. I don't know where one would even begin with this problem.

2. Prove/disprove there are infinitely many primes whose decimal representation does not contain the digit 9. For large n there are roughly n/log(n) primes below it and roughly 9^(log(n)/log(10)) = 9^(log(n)/log(9) * log(9)/log(10)) = n^0.954 numbers that do not contain the digit 9. If we randomly picked n/log(n) numbers from 1..n for say set A and n^0.954 numbers from 1..n for set B, the probability of A and B having no common intersection is something like (1-1/log(n)) ^ (n^0.954) ~ exp(-n^0.954/log(n)) for large n assuming n^0.954 << n/log(n) which is pretty damn close to zero, but of course this isn't really a proof. However this also seems much weaker than one of Landau's problems which states that are infinitely many primes of the form n^2+1 so this one seems like it should be "easier".

This is (conjectured) not only true for base 10, but for every base, there are infinitely many primes contain only 0 and 1 (in fact, not only for 0 and 1, you can choose any two digits d1 and d2 such that gcd(d1,d2) = 1 in any base b), since it is conjectured that for any given form x{d}y in any base b (d is digit in base b, x and y are strings in base b) such that there is no obvious reason why there can’t be a prime (or can be only prime for very small number) of this form (the obvious reason may be "full numeric covering set", "full algebraic covering set", or "partial numeric, partial algebraic covering set"), then there are infinitely many primes of the form x{d}y

For example, there is conjectured to infinitely many primes of the form 10{1} (i.e. 10111...111, which is d = 1, x = string "10", y = empty string, in x{d}y) in any given base, and of course all primes of this form satisfy your condition (primes containing only digits 0 and 1).