20201113, 00:50  #1 
Jan 2012
Toronto, Canada
41 Posts 
Hard recreational math problems
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 (11/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". 
20201113, 01:16  #2  
Feb 2017
Nowhere
3,797 Posts 
Quote:
So it is proven, but don't ask me to explain the proof... Still thinking about first problem... 

20201113, 01:16  #3 
Einyen
Dec 2003
Denmark
3^{2}×331 Posts 
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. Last fiddled with by ATH on 20201113 at 01:19 
20201113, 02:28  #4  
"Ethan O'Connor"
Oct 2002
GIMPS since Jan 1996
2·3^{2}·5 Posts 
Quote:


20201113, 02:43  #5 
Feb 2017
Nowhere
3,797 Posts 
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. 
20201113, 02:45  #6  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·19·241 Posts 
Quote:
There is likely an infinity of primes that are decimal repeated units. 

20201113, 02:54  #7 
Jan 2012
Toronto, Canada
41 Posts 
According to Theorem 1.2 in the paper, given a baseq, an integer s <= q^0.2875, and any baseq digits 0 <= a_1, ..., a_s <= q1, there are infinitely many primes such that the baseq 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.

20201115, 15:44  #8  
Feb 2017
Nowhere
ED5_{16} Posts 
Quote:
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 "bigO constant," while the number of candidate numbers composed of 1's and 0's is "only" of order 2^k, with a modest "bigO" 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" barebones PariGP 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. Code:
? forstep(n=32+1,63,8,v=binary(n);s=sum(i=1,#v,v[i]);r=s%9;if(r==0r==1r==4r==7,c=sum(i=1,#v,10^(#vi)*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==0r==1r==4r==7,c=sum(i=1,#v,10^(#vi)*v[i]);print(c" "factor(c)))) 1011001 Mat([1011001, 1]) 1101001 [11, 1; 101, 1; 991, 1] 1110001 [151, 1; 7351, 1] Code:
? forstep(n=2048+1,4095,8,v=binary(n);s=sum(i=1,#v,v[i]);r=s%9;if(r==0r==1r==4r==7,c=sum(i=1,#v,10^(#vi)*v[i]);print(c" "factor(c)))) <snip> 100010100001 [7, 2; 233, 1; 1409, 1; 6217, 1] <snip> 101111111001 [3, 6; 138698369, 1] <snip> 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. 

20201115, 19:40  #9 
Nov 2016
19×131 Posts 
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, b1) 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, b1), then there are infinitely many integers n>=1 such that (k*b^n+c)/gcd(k+c, b1) 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, b1) 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 
20201115, 19:44  #10  
Nov 2016
19×131 Posts 
Quote:
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). Last fiddled with by sweety439 on 20201115 at 19:48 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fun math problems for today  cuBerBruce  Puzzles  5  20150401 12:22 
Problems for displaying math formulas  alpertron  Forum Feedback  4  20110526 20:37 
Anyone experience problems with USB hard drives?  Jeff Gilchrist  Hardware  10  20110518 13:16 
wow...1 Tb hard drive  ixfd64  Hardware  8  20040603 20:37 
AIslavery / recreational discussion  TauCeti  Soap Box  4  20040407 00:00 