A062775, related to pythagorean triples mod n, some questions and enhancements
Gottfried Helms
helms at uni-kassel.de
Thu Dec 18 17:21:30 CET 2003
Hi Seqfans -
I came across the series A062775 and have some comments, and possibly enhancements.
||> ID Number: A062775
||> URL: http://www.research.att.com/projects/OEIS?Anum=A062775
||>
||> Sequence: 1,4,9,24,25,36,49,96,99,100,121,216,169,196,225,448,289,
||> 396,361,600,441,484, 529,864,725,676,891,1176,841,900,961,
||> 1792,1089,1156, 1225,2376,1369,1444,1521,2400,1681,1764,1849,
||> 2904,2475,2116,2209,4032,2695,2900
||>
||> Name: Number of Pythagorean triples mod n; i.e. number of non-congruent
||> solutions to x^2 + y^2 = z^2 mod n.
||>
||> Comments: a(n) is multiplicative and for a prime p: a(p) = p^2.
||>
||>The starting number of this series is 1.
which I came across by an email in sci.math by an anonymous sender:
> I've noticed that when the moebius function of n is either -1 or +1,then the
> series term is n^2. However when the moebius(n) = 0,then the interesting set
> of numbers that I've given results.
First comment: (on the description)
I'm not able to understand the description under "Name:
"Name: (...) i.e. number of non-congruent solutions to x^2 + y^2 = z^2 mod n."
I have implemented an excel-function to determine the solutions, and this is
reproducing the series perfectly. I don't understand the "non-congruent"-term.
The entries in the sequence are just the sum of all *possible* solutions
to x^2 + y^2 = z^2 mod n.This can simply by brute force be determined by
creating a twodimensional matrix, where all occuring moduli of x^2,y^2 mod n
are determined, and then is checked how many solutions each combined
entry (x^2+y^2) (mod n) for (z^2) (mod n) allows. So the term "non-congruent"
is misleading here in my opinion, since it introduces an idea of using only
a subset of the solutions.
Second comments (on computing data without need of brute force)
The sequence can be seen as a composition of a systematic set of much more
simple sequences.
First observation is: for certain indexes i, the entry a[i] is just the
square of i.
It can be seen very quickly, that the sequence of the i's is just the sequence
of the square-free integers. Let's call this sequence c.
c = [1,2,3, 5,6,7, 10,11, 13,...]
or its squares: the squares of this sequence give one sub-sequence of A062776 .
A1 = [1,4,9, 25,36,49, 100,121, 169,...]
Removing A1 from A, or more precisely removing c from N (sequence of integers>0)
leaves a sequence X1 which was posted as part of the problem in the NG-mail.
A062775: 1,4,9,24,25,36,49,96,99,100,121,216,169,196,225,448,289,396,361,600,441,484,529,864,725,676,891,1176,841,900,961,1792,
c1=1²*c= 1,2,3 5 6 7 10 11 13 14 15 17 19 21 22 23 26 29 30 31
x1= 4 8 9 12 16 18 20 24 25 27, 28 32
x1 was the sequence a posted in the query
it is the sequence of composite integers, which contain squares or higher
powers as factors.
Now the poster asks, what are the values in A062775 at the positions, where x1
points to? Can these values be directly computed from their index similar to
that of the first partial list A1?
My attempt for a solution is as follows, but I did not succeed yet.
Maybe someone else has an idea - or we keep this partial sequence as some "basic".
Let's accordingly to the OP's question build the second partial list from A062775, Ap:
A062775: 1,4,9,24,25,36,49,96,99,100,121,216,169,196,225,448,289,396,361,600,441,484,529,864,725,676,891,1176,841,900,961,1792,
A1 1,4,9, ,25,36,49, ,100,121, ,169,196,225, ,289, ,361, ,441,484,529, ,676, ,841,900,961, ,
Ap ,24, ,96,99, ,216, 448, ,396, ,600, ,864,725, ,891,1176, 1792,
That corresponds to the same operation on the index-sequences:
c1=1²*c= 1,2,3 5 6 7 10 11 13 14 15 17 19 21 22 23 26 29 30 31
xp= 4 8 9 12 16 18 20 24 25 27, 28 32
At xp we can see, that we can it divide in two sublists again:
xp= 4 8 9 12 16 18 20 24 25 27, 28 32
--------------------------------------------------------------------------------------------------------------------------------
c2= 4 8 12 20 24 28
c3= 9 18 27,
c4= 16 32
c5= 25
where each sublist c(i) starts with i^2 and follows with arithmetic progression
according to the basic sequence C of the square-free integers.
This separation in sublists makes sense, since for each sublist, indexing the
original A062775, its entries are also in simple arithmetic progression - just
contamined with a factor, lets call that f(i).
The whole list A062775 now can be written as a table, where the basic index is C,
the sequence of square-free integers.
In this notation the * and ^-operators mean a elementswise operation:
A1: f(1)* 1 * 1 * C^2 = 1/ 1 * 1 * C^2 = 1 * [ 1,4,9, 25,36,49, , ,100,121,...]
A2: f(2)* 4 * 4 * C^2 = 6/ 4 * 16 * C^2 = 24 * [ 1,4,9, 25,36,49, , ,100,121,...]
A3: f(3)* 9 * 9 * C^2 = 11/ 9 * 81 * C^2 = 99 * [ 1,4,9, 25,36,49, , ,100,121,...]
A4: f(4)*16 *16 * C^2 = 28/16 *256 * C^2 = 448 * [ 1,4,9, 25,36,49, , ,100,121,...]
...
A(i): f(i)*i^2*i^2* C^2
The sequences A(i) are then simply mixed, using their indices k pointing with i^2*k
into A062775
A062775 = { A1 , A2 , A3, ... }
Example:
================================================================================================================================
A1 1,4,9, ,25,36,49, ,100,121, ,169,196,225, ,289, ,361, ,441,484,529, ,676, ,841,900,961,
A2 ,24, ,96, ,216, ,600, ,864, 1176,
A3 99, ,396, ,891,
A4 448, 1792
A5 725
...
a(i) = .............
...
================================================================================================================================
A062775: 1,4,9,24,25,36,49,96,99,100,121,216,169,196,225,448,289,396,361,600,441,484,529,864,725,676,891,1176,841,900,961,1792
For each sublist it is obvious, that they have simple arithmetic progression,
depending on their number A(i) and on an additional factor f(i), which unfortu-
nately is not so easy to derive from p.
The sequence of the factors f(i) seem to be somehow the core of the whole
sequence A062775. I did not succeed to determine a general formula depending on i.
The first entries are
f(i) = { 1/1 , 6/4 , 11/9, 28/16, 29/25, .... }
i { 1 2 3 4 5,.... }
Some simplifications can be made, so that a scheme can be seen.
First, for all i=prime f(i) is
i-1 1
f(i)= 1 + ---- * ---
i i
Second, for powers of 2 is
1 1 1 1
f(2^i) = 1 + --- + --- + ... + --- or f(2^i) = 2 - ---------
2 4 2^i 2^(i+1)
Third
For powers of primes the rule seems analoguous to that of the powers of 2,
but I didn't verify that.
Next:
For composite i's it is really difficult. I looks related to the group-orders
or somehow. For i=6 it is interestingly
1 1
f(6) = 1 + --- + ----
2 3
I think, it is reasonable to see the sequence of the f's somehow as the
core of sequence A062775 (and possibly some relates).
Using only the nominators of f would be an interesting, and somehow "core-like"
entry in the database.
An entry for OEIS could be
f . ( 1,6,11,28,29,66,55,120,105,174,131...)
or, possibly more sensible, only the difference to i^2
f' ( 0,2, 2,12, 4,30, 6, 56, 24, 74, 10....)
where we see the simple scheme for i=prime>2
i ( 3, 5, 7, 11
f' ( 2, 4, 6, 10....)
And I would like to find a general formula to determine f for the
composite-indexed entries too, besides the brute force-approach.
Gottfried Helms
-------------------------------------------------------------------------------
Post scriptum:
Since the
"Number of Pythagorean triples mod n;(...) solutions to x^2 + y^2 = z^2 mod n"
is related to the series of square-free composites and primes, it was interesting,
to see, what is about higher exponents.
For the exponent of 3 there is an equivalent entry in OEIS, but not for 4,5,
or higher.
Also it no more true, that for primes i the entry in the analoguous series,
say, A_3[i] is always i^2 - there are different classes of primes obviously.
exp=3: E_3: "(...) number of solutions to x^3 + y^3 = z^3 mod n"
primes p in E_3, which are *not* producing p^2 as entry:
7,13,19,31,37,43,61,67,73,79,97,103,109,127,139,151,157,163,181,193,199,211,223,229,241
This sequence in on OEIS as " primes 6k+1 === 1 mod 3 "
Empirical observation: primes==1 mod 3
exp=4: E_4: "(...) number of solutions to x^4 + y^4 = z^4 mod n"
primes p in E_4, which are *not* producing p^2 as entry:
5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193,197,223,229,241,
This sequence is not on OEIS
Empirical observation: primes==1 mod 4
exp=5: E_5: "(...) number of solutions to x^5 + y^5 = z^5 mod n"
primes p in E_5, which are *not* producing p^2 as entry:
11,31,41,61,71,...
This sequence is not on OEIS
Empirical observation: primes==1 mod 5
For E_3 there are some related sequences in OEIS, but that's again a lot of
stuff...
===========================================================
More information about the SeqFan
mailing list