Computational research note · Giuga numbers
Pick a few different prime numbers. Write down one divided by each of them, add those fractions up, then add or subtract one divided by the product of all your primes. Can you land exactly on 1?
Sometimes you can. Take 2, 3 and 7. Their product is 42, and 1/2 + 1/3 + 1/7 + 1/42 = 21/42 + 14/42 + 6/42 + 1/42, which is exactly 42/42, exactly 1. Take 2, 3 and 5 instead, whose product is 30, and subtract this time: 1/2 + 1/3 + 1/5 − 1/30 = 15/30 + 10/30 + 6/30 − 1/30, again exactly 1. The first kind of solution is called a primary pseudoperfect number, the second a Giuga number, and both are rare enough that every one anybody has ever found can be listed on a single line.
Here is the thing every known solution has in common: the prime 2 is always one of them. Nobody has ever found a solution built only from odd primes, and nobody has been able to rule one out either. That is the open question. It is not a curiosity: Giuga proposed a test for primality in 1950 that is still unresolved, and anything that defeats it would have to be exactly one of these odd solutions.
So the question becomes: if an odd solution exists, how many primes must it use? The more primes you are forced to use, the more remote the thing is. This note takes the question by brute force, with exact whole-number arithmetic and nothing rounded, and shows there is no odd solution of either kind using 12 primes or fewer. A short argument rules out 13. So an odd solution, if there is one, needs at least 14 different odd primes.
results/odd_giuga_official.jsonl), not an estimate. The rungs do not merely grow, the growth itself grows: in the default Candidates view, hover along them and the step from one bar to the next goes 11×, 35×, 515×, then 27,675×. Press Add the m = 13 rung for the hatched bar, which is the one number here that is not measured: it is a lower estimate of roughly 1015 extrapolated from a single m = 13 node the session observed live, against 2.8×1010 for the entire computation to its left. That single node costs about a hundred thousand times everything below it, which is why the certified floor is 14 rather than 16.For Giuga numbers, the number 14 is already on record, attributed to a 1996 paper by Borwein, Borwein, Borwein and Girgensohn. That bound was computed in Maple and the code was never published, so there has been nothing to re-run or check. For odd pseudoperfect numbers the strongest recorded statement was much weaker.
Everything below is the technical version. The figure above is the whole cost argument; the frontier figure in section 4 is the whole result.
A Giuga number is a composite n with p | (n/p − 1) for every prime p | n; a primary pseudoperfect number (PPN) is an n > 1 with 1/n + Σp|n 1/p = 1. All thirteen known Giuga numbers and all ten known PPNs are even; whether odd ones exist is open, and any counterexample to Giuga's 1950 primality conjecture must be an odd Giuga number. The recorded lower bound on the number of prime factors of an odd Giuga number is 14 (secondary: attributed to Borwein, Borwein, Borwein and Girgensohn 1996); for odd PPNs nothing beyond the trivial consequence of Butske, Jaje and Mayernik's complete census (no odd PPN with 8 or fewer prime factors) appears to be recorded.
We prove that the odd members of both families with m prime factors are exactly the odd-prime solution sets of Σ 1/pi + ε/(p1…pm) = 1 (ε = −1 Giuga, ε = +1 PPN) once m ≤ 1411, that m must be even, and we exhaust these equations for all m ≤ 12 by a certified exact branch-and-bound. Every claim below carries its label, in the vocabulary this repository uses throughout: PROVED means a written proof, CERTIFIED means an exact computation with a re-runnable certificate and is true only for the range actually computed, and NUMERICAL would mean evidence only. Nothing on this page is labelled NUMERICAL.
Throughout, p1 < p2 < … < pm are distinct primes, n = p1…pm, A = Σi n/pi, and for ε ∈ {−1, +1} we study
The set {p1,…,pm} solves Eε if and only if A + ε = n. Proof: multiply Eε by n.
For composite squarefree n: p | (n/p − 1) for every prime p | n if and only if T(n) := Σp|n 1/p − 1/n is a positive integer; and a Giuga number is automatically squarefree. The solutions of E−1 in distinct primes with m ≥ 2 are exactly the Giuga numbers with T(n) = 1.
Proof. Squarefreeness: if p2 | n and p | (n/p − 1) then p divides both n/p and n/p − 1, impossible. For squarefree n, T(n) = (A − 1)/n. Modulo any pj, every term n/pi with i ≠ j is divisible by pj, so A − 1 ≡ n/pj − 1 (mod pj). Hence n | A − 1 if and only if pj | (n/pj − 1) for all j, by CRT and squarefreeness. Positivity: A − 1 ≥ 0 always, and A = 1 forces m = 1, excluded by compositeness, so T ∈ ℤ implies T ≥ 1. Finally T = 1 if and only if A − 1 = n, that is, E−1.
An integer n > 1 with 1/n + Σp|n 1/p = 1 is squarefree, and the solutions of E+1 in distinct primes are exactly the PPNs. Every such n satisfies p | (n/p + 1) for all prime p | n, the all-prime, possibly improper, Znám condition.
Proof. If pa exactly divides n with a ≥ 2, multiplying by n gives 1 + Σp n/p = n. Each n/q for q ≠ p is divisible by pa, and n/p by pa−1 ≥ p, so the left side is ≡ 1 (mod p) while the right is ≡ 0, a contradiction. For squarefree n the equation is A + 1 = n, that is E+1; reducing mod pj gives pj | (n/pj + 1).
So the two families, superficially a divisibility condition and a unit-fraction identity, are the two signs of a single equation. That is what lets one engine settle both, and it is why every count in this note comes in a pair.
A composite n satisfies Giuga's congruence Σk=1n−1 kn−1 ≡ −1 (mod n) if and only if n is squarefree and, for every prime p | n, both p | (n/p − 1) and (p−1) | (n/p − 1). Such n is odd, and is in particular a Giuga number, so every lower bound proved here for odd Giuga numbers applies to counterexamples to Giuga's conjecture.
Proof. Fix pa exactly dividing n. Grouping k by residue mod p, the multiples of p contribute 0, and each nonzero residue class has exactly n/p members, so Σ kn−1 ≡ (n/p)·Σr=1p−1 rn−1 (mod p). The inner sum is −1 (mod p) when (p−1) | (n−1) and 0 otherwise. So the congruence forces (p−1) | (n−1) and n/p ≡ 1 (mod p), the latter giving squarefreeness; sufficiency follows by CRT. The identity n − 1 = (p−1)(n/p) + (n/p − 1) converts (p−1) | (n−1) into (p−1) | (n/p − 1). Oddness: if n were even with an odd prime divisor p, then (p−1) | (n−1) fails since n−1 is odd and p−1 even; n = 2 is prime, n = 2a is not squarefree for a ≥ 2, and n = 2p fails p | (n/p − 1) = 1.
The dedicated record for Giuga-conjecture counterexamples is far stronger than anything here: at least 4771 prime factors and more than 1019907 (secondary: Borwein, Maitland and Skerritt 2013). Those objects satisfy strictly more conditions than an odd Giuga number does, so the two bounds are not in competition.
Three facts cut the problem down before any search starts. All three are about the reciprocals of the small odd primes, and the figure below is the whole story.
lemmas.py, not on this plot.Let Sodd(m) be the sum of the reciprocals of the m smallest odd primes. Then Sodd(m) ≤ Sodd(1411) < 2, the partial sums first exceeding 2 at m = 1412. Consequently, for sets of at most 1411 odd primes: on the Giuga side, T = k ≥ 2 would need Σ 1/pi > 2 > Sodd(m), impossible, so T = 1 and E−1 holds; on the PPN side the analogous requirement is Sodd(m) ≥ 2 − 3−m, and lemmas.py certifies Sodd(m) < 2 − 3−m for every m ≤ 1411 by exact rational comparison.
If all pi are odd and {p1,…,pm} solves Eε, then m is even.
Proof. Each n/pi is a product of m − 1 odd primes, hence odd, so A ≡ m (mod 2). By Lemma 1, A = n − ε with n odd and ε = ±1, so A is even.
Lemma 5 is what turns a computation into a bound worth stating. Exhausting m ≤ 12 by itself would only give "at least 13"; parity deletes the 13th rung for free, and the floor becomes 14. It also means the next rung that could improve the result is 14, not 13, and a successful exhaustion there would jump the bound straight to 16.
Sodd(8) < 1 < Sodd(9). Hence an odd solution of E−1 has m ≥ 9, reproducing the classical "an odd Giuga number has at least 9 prime factors", and so does an odd solution of E+1. With Lemma 5, m ≥ 10 in both families before any search runs.
The same exact sweep reproduces the other classical constant in this circle of ideas: the partial sums of 1/p over all primes first exceed 2 at the 59th, which is the standard "at least 59 prime factors" bound for the case T ≥ 2 (secondary: MathWorld). We re-derived 9, 59 and 1412 from scratch in exact rational arithmetic rather than quoting them.
The engine enumerates solution sets of Eε by choosing p1 < p2 < … left to right, carrying the state P = p1…pj, A = Σi≤j P/pi, and the deficit D = P − A. Everything is integer arithmetic; no floating point appears anywhere in the critical path. A claim of exhaustion is only as good as the pruning rules, so each is a lemma.
At any proper prefix of a solution, 0 < A < P, that is D ≥ 1. Proof: a prefix sum A/P ≥ 1 would need the remaining primes to contribute at most 1/n, but the next reciprocal alone exceeds 1/n; and if A/P > 1 the remainder is negative while all future terms are positive.
With deficit d = D/P, t ≥ 3 primes still to choose and p the next prime, any completion satisfies 1/p < d + 1/(3P) and t/p > d − 1/(3P), with the sharper one-sided forms 1/p < d for ε = +1 and t/p > d for ε = −1. The integer bounds the code actually uses, 3P/(3D+1) < p and p ≤ 3Pt/(3D−1), each padded by one, are supersets of these, so no feasible p is ever excluded.
With prefix (P, A) and D ≥ 1, the final two primes q < r satisfy (Dq − P)(Dr − P) = P2 + εD =: N*, with u := Dq − P ≥ 1 and r = (Pq + ε)/u. Moreover gcd(u, D) = 1, so u | (Pq + ε) if and only if u | N*.
This identity is the reason the search terminates at all: the last two primes are not searched, they are read off the divisors of a single integer. The gcd claim is what makes the divisor test valid, and it holds because any common prime of P and D would have to divide A = Σi P/pi, which is nonzero modulo each pi.
With one prime left, pm = (P + ε)/D exactly, and every completed set is re-verified from scratch against A + ε = n. The engine's primality tests are GMP probable-prime, which can only err by calling a composite prime, never the reverse; pruning on a composite verdict is therefore always sound, and a false "prime" can only manufacture a candidate that the final identity and the independent verifier would reject. The one place a pseudoprime could threaten completeness, inside a factorization used for divisor enumeration, is guarded separately: factors are re-verified and any factor at or above 264, beyond the verified BPSW range, is reported per run. Every official run reports none. The C kernel's wheel filter skips a candidate only when some prime at most 61 divides u but not N*, which cannot divide N*.
The soundness direction and the completeness direction are separated deliberately. Soundness failures produce a spurious solution, which the from-definition verifier catches. Completeness failures produce a missed solution, which nothing downstream can catch, so every completeness-relevant step, the windows, the closure, the wheel and the factor bound, is a proved lemma rather than a tested one.
Every odd Giuga number has at least 14 prime factors. Proof: an odd Giuga number with at most 1411 prime factors has T = 1 by Lemma 4, so its prime set solves E−1; the runs exhaust all m ≤ 12 and find nothing, and m = 13 is excluded by Lemma 5.
Every odd primary pseudoperfect number, equivalently every set of distinct odd primes satisfying the all-prime Znám condition with T′ = 1, which below 1412 factors is all of them, has at least 14 prime factors. Proof: as for Theorem A, with Lemma 3 and the E+1 runs.
An exhaustion that finds nothing is worth exactly as much as the evidence that the engine can find something. Run in all-primes mode, the same code reproduces both published censuses term for term.
| Control | Expected | Found | Cost | Label |
|---|---|---|---|---|
| Giuga numbers, at most 8 prime factors | 12 known, complete census (secondary: OEIS A007850) | 12, term for term; 3 of them at 8 factors | 831,968 nodes, 512 s | CERTIFIED |
| Primary pseudoperfect numbers, at most 8 prime factors | 8 known, complete census (secondary: OEIS A054377, Butske–Jaje–Mayernik 2000) | 8, term for term | 510 s | CERTIFIED |
| From-definition verifier on every solution found | all pass | 29 / 29 | instant | CERTIFIED |
Clean-room second engine (engine2.py), odd side | agreement | agrees for every m ≤ 11 | 2 s | CERTIFIED |
| Classical constants 9, 59, 1412 by exact rational sweep | match the literature values | match | ~2 min | PROVED |
The verifier is deliberately not a re-run of the search: it takes each solution set, rebuilds n, checks the rational identity with exact fractions and checks p | (n/p − 1) for every prime factor independently. The second engine shares no code with the first, uses stdlib fractions instead of gmpy2, and derives its own looser windows, so agreement between them is meaningful rather than tautological.
| m | Closure nodes | Closure candidates | Tree nodes | Solutions |
|---|---|---|---|---|
| 8 | 2 | 5 | 20 | none |
| 9 | 8 | 57 | 45 | none |
| 10 | 52 | 1,974 | 73 | none |
| 11 | 924 | 1,016,502 | 1,111 | none |
| 12 | 240,534 | 28,131,218,255 | 242,828 | none |
Counts are from results/odd_giuga_official.jsonl, every row carrying its engine hash and a complete flag. The E+1 ladder has the same closure statistics from m = 10 upward, because ε shifts every window bound by less than an integer once the primes are that large; the two ladders differ at m ≤ 9, and the censuses distinguish the signs decisively. A driver was launched twice by accident, so the odd ladders appear twice in the official files under two engine builds. All closure invariants agree pair for pair; only the tree-node count differs at m = 8 and 9, where a serial run counts frontier nodes that a parallel run hands to the splitter. We kept both passes as an unplanned extra cross-validation, and the table above reports the serial pass.
Direct exhaustion of m = 13 is out of reach for this method on this hardware, and the useful contribution is to say precisely why rather than to report a timeout.
The t = 3 nodes of the m = 13 tree can carry deficits around 10−9. One observed live node had the prefix (3, 5, 7, 11, 13, 17, 19, 23, 967, 101429, 679364479), whose two-primes-left window has width 3.3×1013. A t = 3 node with deficit d branches over every prime in (1/d, 3/d), about 6×107 children at d = 1.5×10−9, and each child is a two-primes-left closure whose own window has width around 109, or else demands factoring N* ≈ P2 ≈ 1050. The summed closure cost of that single node is of order 1015 kernel candidates, against 2.8×1010 for the whole m ≤ 12 tree. That is the hatched bar in the first figure, and it is a factor of roughly 105; m = 14 is two further orders beyond.
The same wall was then measured on the even side, which is the part we did not expect. An attempted 9-factor Giuga census, the first stratum beyond the complete 8-factor census of 1996, ran into the identical structure one level down: live workers profiled at prefixes (2, 3, 7, 43, 1811, ≈654371, ≈1.8×109), chains of near-perfect fills with deficits falling through 10−6, 10−9, 10−12, two-primes-left windows of width around 1012, and fanouts of about 108 primes at t = 3 under roughly 1.3×105 sibling branches. The even 9-factor stratum therefore sits about 105 times beyond the 8-factor census by this method. Butske, Jaje and Mayernik's remark that the next step requires factoring large auxiliary integers understates it: the obstruction is the count of required factorizations, not their size.
That has a consequence worth stating carefully. The literature trail available to this session (secondary: MathWorld and Wikipedia, attributing the 1996 paper) gives "an odd Giuga number has at least 14 prime factors" with no proof and no method. A 1996 Maple exhaustion of the full odd tree through m = 13, in the sense used here, looks implausible by the same accounting: the even 8-factor census, which that paper demonstrably did complete, totals about 105 closures with 20 to 35 digit factorizations, five orders of magnitude cheaper. Their 14 may rest on the sequence and relaxation methods of the paper itself, on structure we have not reproduced, or on the Carmichael-augmented counterexample setting. We make no claim about their derivation. Theorems A and B stand on this session's certificates alone, and at worst they independently certify a recorded constant, which is a perfectly good outcome and is stated as such.
Everything is in the companion repository: the engine (search.py, with the C kernel kernel.c), the clean-room cross-check (engine2.py), the from-definition verifier (verify_solution.py), the exact-rational lemma constants (lemmas.py), the frozen official run set (run_official.sh) and the run records in results/.
| Step | Command |
|---|---|
| Dependencies | python3 -m pip install gmpy2 sympy numpy python-flint |
| Build the kernel | gcc -O2 -shared -fPIC -o kernel.so kernel.c |
| The official runs | ./run_official.sh |
| Verify every solution found | python3 verify_solution.py results/control_giuga_official.jsonl results/control_ppn_official.jsonl |
| Independent engine, overlap range | python3 engine2.py -1 odd 3 11 |
| Lemma constants | python3 lemmas.py |
Environment: 4 cores, 15 GB, Python 3.11.15, gmpy2 2.3.1, sympy 1.14.0, numpy 2.4.6, python-flint 0.9.0, gcc -O2. The odd m = 12 fingerprint, 240,534 closures and summed window width 28,131,218,255, was reproduced identically by five independent traversals across engine versions; every engine change during the session was gated on that battery plus the small censuses on both signs.
This note was produced in a Claude Code research session. The mathematics, the code and the runs were carried out with AI assistance throughout, and that assistance is disclosed here as a matter of policy. No AI system is an author.