[seqfan] New pseudosquares and pseudocubes found: to which OEIS seq are these additions

Jonathan Post jvospost3 at gmail.com
Wed Jan 20 05:11:05 CET 2010

Just posted on arXiv, dated Jan 19, 2010.

Let (x/y) denote the Legendre symbol [5]. For an odd prime p, let Lp,2, the
pseudosquare for p, be the smallest positive integer such that
1. L_p,2 congruent to 1 (mod 8),
2. (L_p,2/q) = 1 for every odd prime q <= p, and
3. L_p,2 is not a perfect square.
In other words, L_p,2 is a square modulo all primes up to p, but is
not a square.
We found the following new pseudosquares:

367..............36553 34429 47705 74600 46489
373..............42350 25223 08059 75035 19329
379..............> 10^25

The two pseudosquares listed were found in 2008 in a computation that went up
to 5 × 1024, taking roughly 3 months wall time. The final computation leading
to the lower bound of 1025 ran for about 6 months, in two 3-month pieces, the
second of which finished on January 1st, 2010.
Wooding and Williams [11] had found a lower bound of L_367,2 > 120120 ×
2^64 ~ 2.216 × 102^4. (Note: a complete table of pseudosquares,
current as of this
writing, is available at http://cr.yp.to/focus.html care of Dan Bernstein).
Similarly, for an odd prime p, let Lp,3, the pseudocube for p, be the

    Title: Sieving for pseudosquares and pseudocubes in parallel using
doubly-focused enumeration and wheel datastructures
    Authors: Jonathan P. Sorenson
    Subjects: Number Theory (math.NT)

    We extend the known tables of pseudosquares and pseudocubes,
discuss the implications of these new data on the conjectured
distribution of pseudosquares and pseudocubes, and present the details
of the algorithm used to do this work. Our algorithm is based on the
space-saving wheel data structure combined with doubly-focused
enumeration, run in parallel on a cluster supercomputer.

More information about the SeqFan mailing list