A024409 - OEIS

%I #35 Mar 19 2026 09:41:52

%S 65,85,145,185,205,221,265,305,325,365,377,425,445,481,485,493,505,

%T 533,545,565,629,685,689,697,725,745,785,793,845,865,901,905,925,949,

%U 965,985,1025,1037,1073,1105,1145,1157,1165,1189,1205,1241,1261,1285,1313,1325

%N Hypotenuses of more than one primitive Pythagorean triangle.

%C The subsequence allowing 4 different shapes is in A159781. [_R. J. Mathar_, Apr 12 2010]

%C A024362(a(n)) > 1. - _Reinhard Zumkeller_, Dec 02 2012

%C From _Jianing Song_, Mar 19 2026: (Start)

%C According to the formula of A024362, this is exactly numbers with only prime factors congruent to 1 modulo 4 that are not prime powers.

%C This sequence lists odd k such that the witnesses for strong pseudoprimality of k do not form a subgroup of (Z/kZ)* (i.e., are not closed under multiplication).

%C Proof. Write k-1 = 2^s*d with odd d. The case where k is a prime power is obvious.

%C If k has a prime factor congruent to 3 modulo 4, then k is a strong pseudoprime in base b if and only if b^d == +-1 (mod k), because b^(2*d) == -1 (mod k) has no solutions. Those b are closed under multiplication.

%C Now suppose that we have k = Prod_{i=1..r} (p_i)^(e_i), with p_i == 1 (mod 4), r > 2. Let v_i be a primitive 4th root of unity modulo (p_i)^(e_i). Consider

%C - a == v_i (mod (p_i)^(e_i));

%C - b == v_i^(2*u_i-1) (mod (p_i)^(e_i)), u_i = 0 or 1.

%C Then ((a*b)^d mod (p_1)^(e_1), ..., (a*b)^d mod (p_r)^(e_r)) = ((-1)^(u_1), ..., (-1)^(u_r)), so (a*b)^d mod k can take 2^r values. On the other hand, note that a^(2*d) == b^(2*d) == -1 (mod k). If k is a strong pseudoprime modulo a*b, then we need to have (a*b)^d == +-1 (mod k), contradiction. (End)

%H Ray Chandler, <a href="/A024409/b024409.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from Reinhard Zumkeller)

%H Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Pythag/pythag.html">Pythagorean Triples and Online Calculators</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Strong_pseudoprime">Strong pseudoprime</a>

%e 65^2 = 16^2 + 63^2 = 33^2 + 56^2 (also = 25^2 + 60^2 = 39^2 + 52^2, but these are not primitive, with gcd = 5 resp. 13). Note that 65 = 1^2 + 8^2 = 4^2 + 7^2 is also the least integer > 1 to be a sum a^2 + b^2 with gcd(a,b) = 1 in two ways. - _M. F. Hasler_, May 18 2023

%t f[c_] := f[c] = Block[{a = 1, b, cnt = 0, lmt = Floor[ Sqrt[c^2/2]]}, While[b = Sqrt[c^2 - a^2]; a < lmt, If[IntegerQ@ b && GCD[a, b, c] == 1, cnt++]; a++]; cnt]Select[1 + 4 Range@ 335, f@# > 1 &] (* _Robert G. Wilson v_, Mar 16 2014 *)

%t Select[Tally[Sqrt[Total[#^2]]&/@Union[Sort/@({Times@@#,(Last[#]^2-First[ #]^2)/2}&/@(Select[Subsets[Range[1,71,2],{2}],GCD@@# == 1&]))]],#[[2]]> 1&][[All,1]]//Sort (* _Harvey P. Dale_, Sep 29 2018 *)

%o (Haskell)

%o import Data.List (findIndices)

%o a024409 n = a024409_list !! (n-1)

%o a024409_list = map (+ 1) $ findIndices (> 1) a024362_list

%o -- _Reinhard Zumkeller_, Dec 02 2012

%o (PARI) isA024409(n) = if(n%2==0||n==1, return(0)); my(f=factor(n)[, 1]~, r=#f); if(r==1, return(0)); for(i=1, r, if(f[i]%4!=1, return(0))); return(1) \\ _Jianing Song_, Mar 19 2026

%Y Cf. A020882, A120960, subsequence of A008846.

%K nonn

%O 1,1

%A _David W. Wilson_