Re: Conjecture in "Mathematical Cranks"

[The Last Danish Pastry]
In Underwood Dudley's fine book "Mathematical Cranks", in the chapter
"Number Theory, The Lure Of", we find the following conjecture
[paraphrased very slightly]:

Every positive integer of the form 4n+3 is the sum of a square and
twice a prime (except for 3 and 79).

Dudley comments that he would bet that the conjecture is false. Does
anybody know any results on this conjecture?

Since it looks likely that it's actually true, did Dudley gave any reason(s)
for betting it's false?

[Tim Peters]
I wrote a little segmented sieve to check, and it's true at least thru 11
million (I got bored then ;-)). In steps of a million:

lo hi min max
-------- -------- --- ---
3 1000003 0 317 0 ways found only at i=3 and i=79
1000003 2000003 10 425
2000003 3000003 13 516
3000003 4000003 17 597
4000003 5000003 21 599
5000003 6000003 24 703
6000003 7000003 26 735
7000003 8000003 27 776
8000003 9000003 26 772
9000003 10000003 31 831
10000003 11000003 32 896

Each row considers all i congruent to 3 modulo 4 in the range
lo <= i < hi. Across all i in range, `min` is the smallest number
of ways to write i as j^2+2*prime found, and `max` the largest.

Through the range tested, the largest m expressible in exactly n ways:

n m
-- -------
0 79
1 11335
2 89959
3 53251
4 130579
5 208531
6 310171
7 419059
8 525079
9 648631
10 1135579

I later used a different program to verify the conjecture through 2^31
(~2.1*10^9). Given the results above, I would have been surprised to find a
counterexample.

Technical trick: note that:

n = 2*p + i^2

implies

n + 4*(i+1) = 2*p + (i+2)^2

That is, if you know n fits the hypothesis, then an infinite sequence of
larger n' (also congruent to 3 modulo 4) also does. For example,

7 = 2*3 + 1^2
so
7 + 4*(1+1) = 15 = 2*3 + 3^2
so
15 + 4*(3+1) = 31 = 2*3 + 5^2
so
31 + 4*(5+1) = 55 = 2*3 + 7^2
so
55 + 4*(7+1) = 87 = 2*3 + 9^2

and so on. So when finding a winning <n, i> pair, a priority queue or
dictionary can be used to record a derived winning <n+4*(i+1), i+2> pair,
and there's no need to check those n' when they come up -- or, in a sieve,
the whole chain of derived n' can be "crossed off" at once. That alone was
enough to decide the fate of about 68% of the candidates through 2^31,
starting with 3 and adding 4 each time around the loop.


.

Relevant Pages

  • my conjecture: n! + prime(n) != m^k
    ... Perhaps you may be interested to check out the conjecture, ... the probability that a number which is not a pth power ... looks like a pth power modulo q, a prime which is 1 mod p, is 1/p. ... that the smallest prime quadratic nonresidue (equivalently, ...
    (sci.math.research)
  • my conjecture: n! + prime(n) != m^k
    ... Perhaps you may be interested to check out the conjecture, ... the probability that a number which is not a pth power ... looks like a pth power modulo q, a prime which is 1 mod p, is 1/p. ... that the smallest prime quadratic nonresidue (equivalently, ...
    (sci.math)
  • Re: About random, primes and statistics
    ... having a residue of 1 and 2 modulo 3. ... In other words, for k successive primes modulo 3, out of the first n ... Of course, it's just a conjecture. ... Does JSH understand how to rigorously state his own conjecture? ...
    (sci.math)
  • Re: Please help: integers modulo n
    ... u not in v + X (modulo i) ... But if my conjecture is false, ... Notice that for x in X: x < i/2 ... ku - kv = i-k not in X ...
    (sci.math)
  • Re: Please help: integers modulo n
    ... Daniel Solomon nous a récemment amicalement signifié: ... u not in v + X (modulo i) ... But if my conjecture is false, ... kv-ku = k in X ...
    (sci.math)