# A062775, related to pythagorean triples mod n, some questions and enhancements / Solution

Gottfried Helms helms at uni-kassel.de
Fri Dec 19 09:59:20 CET 2003

```Hi Seqfans -

Now I've found the solution, how to compute A(i) directly from its
index i for the "irregular" entries of A=A062775 as well as for the
"regular" entries
(See reference for the OEIS-entry at the bottom)

The general formulation for the formula is given in eq [4] below.

------------------------------------------------

As I already wrote, we need a function f of i as a factor to any entry
of A. The function f comes out to be relatively simple, and reflects the
factorial composition of the index i.

Resume the list of A, separated for "regular" and "irregular" entries:

---------------------------------------------------------------------
> A062775:   1,4,9,24,25,36,49,96,99,100,121,216,169,196,225,448,289,
>
> A1         1,4,9,  ,25,36,49,     ,100,121,   ,169,196,225,   ,289,
> Ap              ,24,        ,96,99,       ,216,            448,   ,
>
> That corresponds to the same operation on the index-sequences:
>
> i1=        1,2,3     5  6  7        10  11      13  14  15      17
> ip=               4           8  9          12              16
>
---------------------------------------------------------------------

Now we write the elements of A as a function of its index

A(i) = h(i)*i^2

As it is obvious, the function h(i) must be 1 for the squarefree elements
of the index i. It came out, that it is completely determined by the factorial
composition of i for the "irregular" elements of A. Since for this function
only a part of i's prime-factors is relevant, we write (and define) another
function f, which only works on this interesting part.

A(i) = f(j) * i^2

where
j = some_part_of_primefactors(i)

------------------------------------------------------------------

Assume any index i with the following composition of prime-powers

i = a^2 * b^5 * c^6 * d * e

where a,b,c,d,e are all different primes

Then separate this number into a squares-part  and a square-free-part

i = (a * b^2 * c^3)^2   * ( b*d*e)

Note, that the odd 5th power of b leads to spreading b in both parentheses.
The new function f uses only the part in the left parentheses, the components
in i, which are present in squared-form.

Let j be the root of the squares-part of i:

j = (a * b^2 * c^3)

then the general formula for determining A(i) is

A(i) = f(j)*i^2

The functional definition of f is: ============================

1) For the unit 1, f is

[1]       f(1) = 1

2) For any power k (k>=1) of a prime p the value of f is:

/ 1     if p=2
[2]   f(p^k) = 1 + (1 - 1/p^k) * |
\ 1/p   if p>2

3) For any pair or list of composites, collected to powers of primes,
so that the prime-factors in a,b,... are mutally different, f is

[3]   f(a * b * ... ) = f(a) * f(b) * ...

f(p^k * q^i * r^j * ... ) = f(p^k) * f(q^i) * f(r^j) * ...

Thus, to determine f(j), j has to be decomposed into its prime-factors,
and f(j) is just the product of all f's of the powers of the prime-factors
of j.

4) General formulation:

For an index, and r,s,...,p,q,... all different primes

2j     2k+1
i = r*s*...* p    * q    *   ...

the entry of A(i) is:
1     1               1    1
[4a]    A(i) = i^2 * [1 + (1 - ---- )-- ] [1 + (1 - ---- )-- ] ...
p^j   p              q^k   q

If one of the prime-powers is a power of 2 , for instance p=2 then
the single 1/p - fraction vanishes:

1     1               1    1
[4b]    A(i) = i^2 * [1 + (1 - ---- )-- ] [1 + (1 - ---- )-- ] ...
p^j   1              q^k   q

------------------------------------------------------------------------

Example : ==================================================

Let's check the 12. entry of A (=A062775)

i = 12
=  2^2 * 3

j is the square-root of the squared prime-factors in i
j = 2

Now
f(j) = f(2)
1
= (1+ (1 - --- ) )
2

3
=   ---
2

And
3
A(12) = f(j)*i^2 = ---- * 12^2
2

= 3 * 6 * 12
A(12) = 216

This result matches the entry A(12) of the given list.

------------------------------------
A more general example:

Let's check the 600. entry of A (=A062775)

i = 600
=  2^3 * 3 * 5^2
=  (2 * 5)^2 * (2*5)

j is the square-root of the squared prime-factors in i

j = 2*5

Now
f(j) = f(2*5)
= f(2) * f(5)
1                1      1
= (1+ (1 - --- ) ) * (1+ (1- ---) * --- )
2                5      5

3       29
=   ---  *  ---
2       25

87
=  -----
50

And
87
A(600) = f(j)*i^2 = ---- * 600^2
50

= 87 * 12 * 600
A(600) = 626400

which matches the result of the brute-force (counting) method.

----------------------------

This function is only empirically derived from present results of
the counting-method, thus should be derived algebraically, if this
is possible.

The extension to higher exponents of the basic problem ( number of
solutions of x^2 + y^2 = z^2  modulo n ) could not be given yet, and

Gottfried Helms

================================================================

Appendix: reference for the sequence A

---------------------------------
||> 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.

Anonymous wrote:

> 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.

```