OFFSET
1,1
COMMENTS
The subsequence allowing 4 different shapes is in A159781. [R. J. Mathar, Apr 12 2010]
A024362(a(n)) > 1. - Reinhard Zumkeller, Dec 02 2012
From Jianing Song, Mar 19 2026: (Start)
According to the formula of A024362, this is exactly numbers with only prime factors congruent to 1 modulo 4 that are not prime powers.
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).
Proof. Write k-1 = 2^s*d with odd d. The case where k is a prime power is obvious.
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.
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
- a == v_i (mod (p_i)^(e_i));
- b == v_i^(2*u_i-1) (mod (p_i)^(e_i)), u_i = 0 or 1.
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)
LINKS
Ray Chandler, Table of n, a(n) for n = 1..10000 (first 1000 terms from Reinhard Zumkeller)
Ron Knott, Pythagorean Triples and Online Calculators
Wikipedia, Strong pseudoprime
EXAMPLE
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
MATHEMATICA
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 *)
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 *)
PROG
(Haskell)
import Data.List (findIndices)
a024409 n = a024409_list !! (n-1)
a024409_list = map (+ 1) $ findIndices (> 1) a024362_list
-- Reinhard Zumkeller, Dec 02 2012
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved