10 is a square mod p (A038879 OEIS)

[Davide Rotondo]

Hi to all seqfan, today I noticed that the sequence of prime numbers p such that 10 is a square mod p (A038879 OEIS), consists of the union of
A141179
Primes of the form 3*x^2 + 2*x*y - 3*y^2 (as well as of the form 3*x^2 + 8*x*y + 2*y^2), and of
A141180
Primes of the form x^2+6*x*y-y^2 (as well as of the form 6*x^2+8*x*y+y^2).

What do you think?

regards

Davide

[Gareth McCaughan]

According to the sequences' entries:

A141179 consists of primes that are one of +- 13,37,43,53 mod 120.

A141180 consists of primes such that (p^2-1)/24 is a multiple of 10;
that is, such that p^2 = 1 mod 240; that is, such that p is one of
1,31,41,49,71,79,89,119 mod 120.

So the union of these consists of primes that are one of
1,13,31,37,41,43,49,53,67,71,77,79,83,89,107,119 mod 120.

On the other hand, A038879 consists of (2 and 5, and also) primes that
are +- 1,3,9,13 mod 40; that is, 1,3,9,13,27,31,37,39 mod 40; it's easy
to see that this is the same set of primes.

A higher-brow way of looking at it: 3*x^2 + 2*x*y - 3*y^2 and
x^2+6*x*y-y^2 are (up to equivalence) the two distinct quadratic forms
of discriminant 40. If p is a prime not dividing D, then p is
representable by _some_ quadratic form of discriminant D iff D is a
square mod p. Clearly 40 is a square mod p iff 10 is a square mod p.

So I'm afraid this observation isn't a surprise :-).

--
g

[Christopher Landauer]

Hihi, all -



These are results for two searches:

Minimum area convex lattice n-gons in file results_n1040a_announce.txt;

Minimum L1-perimeter convex lattice n-gons in file results_n1040p_announce.tx
(I did this one because it was trivial to code, given the area search programs, is faster to compute,
and seems to provide a very good upper bound for minimum area: the smallest n that differs is n=21).

Each file is about 22KB, a little over 1070 lines, all ASCII text.
I don't know to provide these files to the OEIS most appropriately
(I'm pretty sure that I cannot just attach them here, but I tried that anyway).

Complication

GL(2, Z) preserves area, SL(2, Z) preserves oriented area,
so we need to use some other criteria to reduce the search (i.e., make it finite and even relatively small).
The ones I chose were:
A minimum area;
X minimum L1-perimeter (actually, a euphemism that is easier to compute);
L minimum maxl (maxl is maximum edge L1-length).

The programs used combined criterion XAL for L1-perimeter
(first X, then A among X winners, then L among those winners).
For this search, the linear groups are irrelevant.

The programs used combined criteria AXL and ALX for area.
These results differ for n <= 1040 only at n=275 and n=872.

In both searches,
I call polygons that satisfy these three combined criteria
``winner'' polygons for the respective combined criterion
(recognizing that there are usually many such winner polygons
for each combined criterion).
These combined criteria are not enough for uniqueness,
but the programs I wrote only try to find one winner polygon
(later versions will find many, I hope all).

Strategy

My approach was to choose b = maximum allowed L1-length of an edge
(which limits all possible edges of minimal convex lattice polygons to a small set
related to Farey sequences, easily computable given b),
then increase b until no further changes occur.
For example,
if we take b = 45, then we write the limit as b045,
and just to keep the notations clear,
if we are using b=35 for L1-perimeter,
we write b035p
(there were thousands of files,
some several terabytes long,
and I put these notations into the file names so I would know what I was looking at
without having to look inside the file).

I write ``margin'' for the difference between the imposed edge L1-length bound b
and the maximum edge L1-length needed.

Numerous early examples showed that margin = 1 is not enough,
since increasing b in that case often led to better (smaller) results.
However,
margin 2 was enough for all the computations up to n = 1040,
because increasing b when the margin was 2 never produced better results.
I ran the programs with even larger margins
(i.e., larger edge L1-length bounds b than seemed to be necessary)
because I have no proof that 2 is always enough
(or, indeed, what the maximum edge L1-length is for a given n).

Based on the ``even n theorem'' (about symmetry),
and an ``odd n conjecture'' (a related property that I observed for odd n up to about 100,
and then assumed for the basic search, but also tested up to n=1040),
the programs actually only compute ``polyhalves'',
which are convex polygons that can be about half of a winner polygon
(so a polyhalf has one long edge that will be interior to the polygon),
and then stitch them together in an obvious way to make polygons,
from which winners are selected.
These polyhalves are computed incrementally with a dynamic programming approach,
and their parameters are the contents of the intermediate files;
finding them takes the bulk of the compute time
(the stitching together is relatively quick).

History

I first read about this problem in a 10 September 2001 e-mail on the math-fun mailing list,
when the first unknown case was n=11
(which I thought would be easy),
and have been working on it assiduously since then,
with several multi-year gaps while I waited for larger disks and faster machines,
or for a new idea in the algorithm or the data format
promising another computation time or file size reduction.
After numerous changes and several complete rewrites,
many incorporating the results of comments on math-fun,
the current program is roughly 5 or 6 orders of magnitude faster than the first one I wrote.
Even so,
these results took somewhere between 15 and 20 CPU years on several commodity PCs and laptops
(all the programs were written in C),
mostly running FreeBSD, with some on Ubuntu Linux, and a small number on Mac OSX.
The intermediate files that were produced for the latest results take about 36 TB
(29 TB for area and 7 TB for L1-perimeter),
but there were several hundred TB in thousands of files generated overall,
many of which were individually over 200GB.

What remains is to convert those intermediate polyhalf files into actual example polygons,
which will take a few weeks to write the program
(I expect execution time to be much faster).
The problem is that I wrote the conversion program once before,
when the intermediate polyhalf data was first ready in 2022,
then fat finger deleted it (grumble grumble),
which made me so mad I haven't been able to go back to it before now.

Of course,
it must also be remembered that these results were generated by computer programs,
so there could still be any number of errors,
but since multiple programs agreed on the small values
(I made sure that each new iteration agreed with the previous one),
and all of the corresponding results that are already in the OEIS
(a070911 for all values up to n=150,
and a089187 for even only up to n=200,
since the evens are much faster to compute)
are the same,
I am pretty confident in these values.

Next

Much more detail about the search algorithm and its development,
including credit to the many people whose suggestions I used,
will be made available,
along with some technical discussion of my choices
(e.g., why use L1? What reductions are compatible with the combined criteria?),
and some interesting questions to pursue
(e.g., what are the SL(2, Z) and GL(2, Z) equivalence classes of winner polygons?
Are there classes that only have very large minimum values of maxl?).


More later,
chris

[Davide Rotondo]

Thnks Gareth.

Davide

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/54acfdcb-4ce6-4a70-af87-a513f8f9d366%40pobox.com.

[Marc LeBrun]

Although it may not be a "surprise", it seems like it might be worthwhile to add comments to enrich A038879:

Davide, please consider submitting a comment noting that A038879 is the union of A141179 and A141180.

Gareth, please consider contributing a comment summarizing your "higher-brow" proof.

While abstaining from dilutive banality is always good, keep in mind that it's sometimes potentially valuable to future OEIS users when you explicitly include interesting facts and non-obvious relationships of sequences, thereby "denormalizing" some relevant mathematical knowledge and caching it in the OEIS, rather than just leaving it to evaporate in the email thread here.  Not everything has to resolve the GRH or Collatz conjecture to be useful or interesting!

Thanks!

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAJu53H83%3DBK1B77rz%2BV%2BYBuAa1FOSkBLLsPuX7so5rYvxfG3wg%40mail.gmail.com.

[Gareth McCaughan]

On 19/11/2025 20:34, Marc LeBrun wrote:

Although it may not be a "surprise", it seems like it might be worthwhile to add comments to enrich A038879:

Davide, please consider submitting a comment noting that A038879 is the union of A141179 and A141180.

Gareth, please consider contributing a comment summarizing your "higher-brow" proof.

While abstaining from dilutive banality is always good, keep in mind that it's sometimes potentially valuable to future OEIS users when you explicitly include interesting facts and non-obvious relationships of sequences, thereby "denormalizing" some relevant mathematical knowledge and caching it in the OEIS, rather than just leaving it to evaporate in the email thread here.  Not everything has to resolve the GRH or Collatz conjecture to be useful or interesting!

If we did this, then surely for every discriminant D we should find the OEIS sequences of positive integers represented by quadratic forms of discriminant D and add a note that the union of these = the sequence of primes mod which D is a quadratic residue. There's nothing very special about D=40.

That seems like quite a lot of work. Maybe it's worth doing, but it's not entirely clear to me that it is.

--
g

[Marc LeBrun]

> If we did this, then surely for every discriminant D we should find the OEIS sequences of positive integers represented by quadratic forms of discriminant D
> and add a note that the union of these = the sequence of primes mod which D is a quadratic residue. There's nothing very special about D=40.
> That seems like quite a lot of work. Maybe it's worth doing, but it's not entirely clear to me that it is.

Gareth, thanks for thoughtfully considering the opportunity to contribute.

Personally I don't see this sort of situation as that kind of all-or-nothing proposition--that feels to me analogous to my saying "I won't help anyone because I can't afford to be charitable to everyone." Of course others may see it differently.

I agree there's nothing intrinsically special about D=40. However looking at A378295 I don't see the string "40" anywhere, and it's at least naively interesting when one encounters 3-way relationships between existing OEIS sequences of the form x = f(y,z) where x, y, and z are (by editorial proviso) interesting.

While most values of D may remain forever obscure, in this instance we actually have an existence proof that at least one OEIS user (Davide) had interests that somehow led to finding this particular case that became a learning opportunity, and at least one OEIS contributor (Gareth) found enough personal value to take the trouble to make this a "teachable moment".

I certainly learned something--for which I thank y'all--and it just seemed a shame to withhold this bit of value from easy capture by the OEIS--sort of like dropping a coin in a cup while passing by...

Perhaps also future automation may reduce the burden of revealing such relationships.

[Davide Rotondo]

Thank you so much, Marc. Unfortunately, I can't submit anything to the Oeis until June 2026. I'd appreciate it if you could do it. If you can't, I'll wait until June 2026.

Regards

Davide

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/670CF375-6748-4B63-863B-9D01A47515AE%40gmail.com.

[Jonas Karlsson]

Marc writes:

> Gareth, thanks for thoughtfully considering the opportunity to contribute. 

...but Gareth has *already* contributed, in fact more than anyone else in this thread. So I don't see why it should be his responsibility to do even more, especially since he feels that the fact is not interesting. (I agree with him, for what it's worth.)

Jonas

[Marc LeBrun]

> ...but Gareth has *already* contributed, in fact more than anyone else in this thread. So I don't see why it should be his responsibility to do even more, especially since he feels that the fact is not interesting. (I agree with him, for what it's worth.)

Right. No one has any responsibility to contribute anything to the OEIS. My intent is simply to encourage people to consider submitting comments instead of having everything just die out in email threads when it doesn't meet the bar for a Millennium Prize. Perhaps this example was ill-chosen; my apologies if so.