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
is left to interested readers.
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.
More information about the SeqFan
mailing list