A005089 -id:A005089 - cp's OEIS frontend

A001221 Number of distinct primes dividing n (also called omega(n)).

0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 3, 1, 2, 2, 1, 2, 3, 1, 2, 2, 3, 1, 2, 1, 2, 2, 2, 2, 3, 1, 2, 1, 2, 1, 3, 2, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 2, 3, 2, 1, 2, 1, 3, 2

Offset: 1

N. J. A. Sloane

From Peter C. Heinig (algorithms(AT)gmx.de), Mar 08 2008: (Start)
This is also the number of maximal ideals of the ring (Z/nZ,+,*). Since every finite integral domain must be a field, every prime ideal of Z/nZ is a maximal ideal and since in general each maximal ideal is prime, there are just as many prime ideals as maximal ones in Z/nZ, so the sequence gives the number of prime ideals of Z/nZ as well.
The reason why this number is given by the sequence is that the ideals of Z/nZ are precisely the subgroups of (Z/nZ,+). Hence for an ideal to be maximal it has form a maximal subgroup of (Z/nZ,+) and this is equivalent to having prime index in (Z/nZ) and this is equivalent to being generated by a single prime divisor of n.
Finally, all the groups arising in this way have different orders, hence are different, so the number of maximal ideals equals the number of distinct primes dividing n. (End)
Equals double inverse Mobius transform of A143519, where A051731 = the inverse Mobius transform. - Gary W. Adamson, Aug 22 2008
a(n) is the number of unitary prime power divisors of n (not including 1). - Jaroslav Krizek, May 04 2009 [corrected by Ilya Gutkovskiy, Oct 09 2019]
Sum_{d|n} 2^(-A001221(d) - A001222(n/d)) = Sum_{d|n} 2^(-A001222(d) - A001221(n/d)) = 1 (see Dressler and van de Lune link). - Michel Marcus, Dec 18 2012
Up to 2*3*5*7*11*13*17*19*23*29  - 1 = 6469693230 - 1, also the decimal expansion of the constant 0.01111211... = Sum_{k>=0} 1/(10 ^ A000040(k) - 1) (see A073668). - Eric Desbiaux, Jan 20 2014
The average order of a(n): Sum_{k=1..n} a(k) ~ Sum_{k=1..n} log log k. - Daniel Forgues, Aug 13-16 2015
From Peter Luschny, Jul 13 2023: (Start)
We can use A001221 and A001222 to classify the positive integers as follows.
   A001222(n) = A001221(n) = 0 singles out {1}.
Restricting to n > 1:
   A001222(n)^A001221(n) = 1: A000040, prime numbers.
   A001221(n)^A001222(n) = 1: A246655, prime powers.
   A001222(n)^A001221(n) > 1: A002808, the composite numbers.
   A001221(n)^A001222(n) > 1: A024619, complement of A246655.
   n^(A001222(n) - A001221(n)) = 1: A144338, products of distinct primes. (End)
Inverse Möbius transform of the characteristic function of primes (A010051). - Wesley Ivan Hurt, Jun 22 2024
Dirichlet convolution of A010051(n) and 1. - Wesley Ivan Hurt, Jul 15 2025

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 844.
G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, pp. 48-57.
J. Peters, A. Lodge and E. J. Ternouth, E. Gifford, Factor Table (n<100000) (British Association Mathematical Tables Vol.V), Burlington House/Cambridge University Press London 1935.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane and Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 from NJAS)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Henry Bottomley, Prime factors calculator
J. Brennen, Prime Factoring Applet
J. Britton, Prime Factorization Machine
A. Dendane, Prime Factors Calculator
Robert E. Dressler and Jan van de Lune, Some remarks concerning the number theoretic functions omega and Omega, Proc. Amer. Math. Soc. 41 (1973), 403-406
J. Flament, Decomposition d'un nombre en facteurs premiers
G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number, Quart. J. Math. 48 (1917), 76-92. Also Collected papers of Srinivasa Ramanujan, AMS Chelsea Publ., Providence, RI (2000): 262-275.
A. Hodges, Java Applet for Factorisation
M. Kac, Statistical Independence in Probability, Analysis and Number Theory, Carus Monograph 12, Math. Assoc. Amer., 1959, see p. 64.
S. O. S. Math, Prime factorization of the first 1000 integers
K. Matthews, Factorization and calculating phi(n),omega(n),d(n),sigma(n) and mu(n)
J. Moyer, "Prime Factors of Integers" server for numbers up to 10^36
Primefan, The First 2500 Integers,Factored
Primefan, Factorer
F. Richman, Factoring into Primes
Eric Weisstein's World of Mathematics, Distinct Prime Factors
Eric Weisstein's World of Mathematics, Moebius Transform
Eric Weisstein's World of Mathematics, Prime Factor
Eric Weisstein's World of Mathematics, Prime zeta function primezeta(s).
Wikipedia, Prime factor
Wikipedia, Table of prime factors
G. Xiao, WIMS server, Factoris
Index entries for "core" sequences
Index entries for sequences computed from exponents in factorization of n

Cf. A001222 (primes counted with multiplicity), A046660, A285577, A346617. Partial sums give A013939.
Cf. also A125666, A069010, A087624, A091202, A091221, A143519, A144494, A158210, A156542, A156552, A000010, A008683.
Sum of the k-th powers of the primes dividing n for k=0..10: this sequence (k=0), A008472 (k=1), A005063 (k=2), A005064 (k=3), A005065 (k=4), A351193 (k=5), A351194 (k=6), A351195 (k=7), A351196 (k=8), A351197 (k=9), A351198 (k=10).
Sequences of the form n^k * Sum_{p|n, p prime} 1/p^k for k=0..10: this sequence (k=0), A069359 (k=1), A322078 (k=2), A351242 (k=3), A351244 (k=4), A351245 (k=5), A351246 (k=6), A351247 (k=7), A351248 (k=8), A351249 (k=9), A351262 (k=10).

import Math.NumberTheory.Primes.Factorisation (factorise)
a001221 = length . snd . unzip . factorise
-- Reinhard Zumkeller, Nov 28 2015

using Nemo
function NumberOfPrimeFactors(n; distinct=true)
    distinct && return length(factor(ZZ(n)))
    sum(e for (p, e) in factor(ZZ(n)); init=0)
end
println([NumberOfPrimeFactors(n) for n in 1:60]) # Peter Luschny, Jan 02 2024

[#PrimeDivisors(n): n in [1..120]]; // Bruno Berselli, Oct 15 2021

A001221 := proc(n) local t1, i; if n = 1 then return 0 else t1 := 0; for i to n do if n mod ithprime(i) = 0 then t1 := t1 + 1 end if end do end if; t1 end proc;
A001221 := proc(n) nops(numtheory[factorset](n)) end proc: # Emeric Deutsch
omega := n -> NumberTheory:-NumberOfPrimeFactors(n, 'distinct'): # Peter Luschny, Jun 15 2025

Array[ Length[ FactorInteger[ # ] ]&, 100 ]
PrimeNu[Range[120]]  (* Harvey P. Dale, Apr 26 2011 *)

func(nops(numlib::primedivisors(n)), n):

numlib::omega(n)$ n=1..110 // Zerinvary Lajos, May 13 2008

PARI
```
a(n)=omega(n)
```

from sympy.ntheory import primefactors
print([len(primefactors(n)) for n in range(1, 1001)])  # Indranil Ghosh, Mar 19 2017

def A001221(n): return sum(1 for p in divisors(n) if is_prime(p))
[A001221(n) for n in (1..80)] # Peter Luschny, Feb 01 2012

[sloane.A001221(n) for n in (1..111)] # Giuseppe Coppoletta, Jan 19 2015

[gp.omega(n) for n in range(1,101)] # G. C. Greubel, Jul 13 2024

G.f.: Sum_{k>=1} x^prime(k)/(1-x^prime(k)). - Benoit Cloitre, Apr 21 2003; corrected by Franklin T. Adams-Watters, Sep 01 2009
Dirichlet generating function: zeta(s)*primezeta(s). - Franklin T. Adams-Watters, Sep 11 2005
Additive with a(p^e) = 1.
a(1) = 0, a(p) = 1, a(pq) = 2, a(pq...z) = k, a(p^k) = 1, where p, q, ..., z are k distinct primes and k natural numbers. - Jaroslav Krizek, May 04 2009
a(n) = log_2(Sum_{d|n} mu(d)^2). - Enrique Pérez Herrero, Jul 09 2012
a(A002110(n)) = n, i.e., a(prime(n)#) = n. - Jean-Marc Rebert, Jul 23 2015
a(n) = A091221(A091202(n)) = A069010(A156552(n)). - Antti Karttunen, circa 2004 & Mar 06 2017
L.g.f.: -log(Product_{k>=1} (1 - x^prime(k))^(1/prime(k))) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, Jul 30 2018
a(n) = log_2(Sum_{k=1..n} mu(gcd(n,k))^2/phi(n/gcd(n,k))) = log_2(Sum_{k=1..n} mu(n/gcd(n,k))^2/phi(n/gcd(n,k))), where phi = A000010 and mu = A008683. - Richard L. Ollerton, May 13 2021
Sum_{k=1..n} 2^(-a(gcd(n,k)) - A001222(n/gcd(n,k)))/phi(n/gcd(n,k)) = Sum_{k=1..n} 2^(-A001222(gcd(n,k)) - a(n/gcd(n,k)))/phi(n/gcd(n,k)) = 1, where phi = A000010. - Richard L. Ollerton, May 13 2021
a(n) = A005089(n) + A005091(n) + A059841(n) = A005088(n) +A005090(n) +A079978(n). - R. J. Mathar, Jul 22 2021
From Wesley Ivan Hurt, Jun 22 2024: (Start)
a(n) = Sum_{p|n, p prime} 1.
a(n) = Sum_{d|n} c(d), where c = A010051. (End)

A009003 Hypotenuse numbers (squares are sums of 2 nonzero squares).

Original entry on oeis.org

5, 10, 13, 15, 17, 20, 25, 26, 29, 30, 34, 35, 37, 39, 40, 41, 45, 50, 51, 52, 53, 55, 58, 60, 61, 65, 68, 70, 73, 74, 75, 78, 80, 82, 85, 87, 89, 90, 91, 95, 97, 100, 101, 102, 104, 105, 106, 109, 110, 111, 113, 115, 116, 117, 119, 120, 122, 123, 125, 130, 135, 136, 137, 140

Offset: 1

David W. Wilson

nonn

Multiples of Pythagorean primes A002144 or of primitive Pythagorean triangles' hypotenuses A008846. - Lekraj Beedassy, Nov 12 2003
This is exactly the sequence of positive integers with at least one prime divisor of the form 4k + 1. Compare A072592. - John W. Layman, Mar 12 2008 and Franklin T. Adams-Watters, Apr 26 2009
Circumradius R of the triangles such that the area, the sides and R are integers. - Michel Lagneau, Mar 03 2012
The 2 squares summing to a(n)^2 cannot be equal because sqrt(2) is not rational. - Jean-Christophe Hervé, Nov 10 2013
Closed under multiplication. The primitive elements are those with exactly one prime divisor of the form 4k + 1 with multiplicity one, which are also those for which there exists a unique integer triangle = A084645. - Jean-Christophe Hervé, Nov 11 2013
a(n) are numbers whose square is the mean of two distinct nonzero squares. This creates 1-to-1 mapping between a Pythagorean triple and a "Mean" triple. If the Pythagorean triple is written, abnormally, as {j, k, h} where j^2 +(j+k)^2 = h^2, and h = a(n), then the corresponding "Mean" triple with the same h is {k, 2j, h} where (k^2 + (k+2j)^2)/2 = h^2. For example for h = 5, the Pythagorean triple is {3, 1, 5} and the Mean triple is {1, 6, 5}. - Richard R. Forberg, Mar 01 2015
Integral side lengths of rhombuses with integral diagonals p and q (therefore also with integral areas A because A = pq/2 is some multiple of 24). No such rhombuses are squares. - Rick L. Shepherd, Apr 09 2017
Conjecture: these are bases n in which exists an n-adic integer x satisfying x^5 = x, and 5 is the smallest k>1 such that x^k =x (so x^2, x^3 and x^4 are not x). Example: the 10-adic integer x = ...499879186432 (A120817) satisfies x^5 = x, and x^2, x^3, and x^4 are not x, so 10 is in this sequence. See also A120817, A210850 and A331548. - Patrick A. Thomas, Mar 01 2020
Didactic comment: When students solve a quadratic equation a*x^2 + b*x + c = 0 (a, b, c: integers) with the solution formula, they often make the mistake of calculating b^2 + 4*a*c instead of b^2 - 4*a*c (especially if a or c is negative). If the root then turns out to be an integer, they feel safe. This sequence lists the absolute values of b for which this error can happen. Reasoning: With p^2 = b^2 - 4*a*c and q^2 = b^2 + 4*a*c it follows by addition immediately that p^2 + q^2 = 2*b^2. If 4*a*c < 0, let p = x + y and q = x - y. If 4*a*c > 0, let p = x - y and q = x + y. In both cases follows that y^2 + x^2 = b^2. So every Pythagorean triple gives an absolute value of b for which this error can occur. Example: From (y, x, b) = (3, 4, 5) follows (q^2, b^2, p^2) = (1, 25, 49) or (p^2, b^2, q^2) = (1, 25, 49) with abs(4*a*c) = 24. - Felix Huber, Jul 22 2023
Conjecture: Numbers m such that the limit: Limit_{s->1} zeta(s)*Sum_{k=1..m} [k|m]*A008683(k)*(i^k)/(k^(s - 1)) exists, which is equivalent to numbers m such that abs(Sum_{k=1..m} [k|m]*A008683(k)*(i^k)) = 0. - Mats Granvik, Jul 06 2024

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 98-104.

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
R. Chapman, Pythagorean triples and sums of squares
Steven R. Finch, Landau-Ramanujan Constant [Broken link]
Steven R. Finch, Landau-Ramanujan Constant [From the Wayback machine]
Ron Knott, Pythagorean Triples and Online Calculators
J. Pahikkala, On contraharmonic mean and Pythagorean triples, Elemente der Mathematik, 65:2 (2010), 62-67.
Patrick A. Thomas, Solutions of x^5=x up to base 100
Index entries for sequences related to sums of squares

Cf. A000404 (sums of 2 squares), A004431 (sums of 2 distinct squares), A009000 (hypotenuse numbers with repetition), A072592, A004613, A187811.
Complement of A004144. Primes in this sequence give A002144. Same as A146984 (integer contraharmonic means) as sets - see Pahikkala 2010, Theorem 5.
Cf. A083025, A084645 (primitive elements), A084646, A084647, A084648, A084649, A006339.

import Data.List (findIndices)
a009003 n = a009003_list !! (n-1)
a009003_list = map (+ 1) $ findIndices (> 0) a005089_list
-- Reinhard Zumkeller, Jan 07 2013

isA009003 := proc(n)
    local p;
    for p in numtheory[factorset](n) do
        if modp(p,4) = 1 then
            return true;
        end if;
    end do:
    false;
end proc:
for n from 1 to 200 do
    if isA009003(n) then
        printf("%d,",n) ;
    end if;
end do: # R. J. Mathar, Nov 17 2014

f[n_] := Module[{k = 1}, While[(n - k^2)^(1/2) != IntegerPart[(n - k^2)^(1/2)], k++; If[2 * k^2 >= n, k = 0; Break[]]]; k]; A009003 = {}; Do[If[f[n^2] > 0, AppendTo[A009003, n]], {n, 3, 100}]; A009003 (* Vladimir Joseph Stephan Orlovsky, Jun 15 2009 *)
Select[Range[200], Length[PowersRepresentations[#^2, 2, 2]] > 1 &] (* Alonso del Arte, Feb 11 2014 *)

is_A009003(n)=setsearch(Set(factor(n)[,1]%4),1)  \\ M. F. Hasler, May 27 2012

list(lim)=my(v=List(),u=vectorsmall(lim\=1)); forprimestep(p=5,lim,4, forstep(n=p,lim,p, u[n]=1)); for(i=5,lim, if(u[i], listput(v,i))); u=0; Vec(v) \\ Charles R Greathouse IV, Jan 13 2022

from itertools import count, islice
from sympy import primefactors
def A009003_gen(): # generator of terms
    return filter(lambda n:any(map(lambda p: p % 4 == 1,primefactors(n))),count(1))
A009003_list = list(islice(A009003_gen(),20)) # Chai Wah Wu, Jun 22 2022

A005089(a(n)) > 0. - Reinhard Zumkeller, Jan 07 2013
a(n) ~ n. - Charles R Greathouse IV, Jan 13 2022
a(n) = sqrt(n-th square in A000404), where A000404 lists the sums of two nonzero squares. - M. F. Hasler, Jun 20 2025

Definition edited by Jean-Christophe Hervé, Nov 10 2013

A083025 Number of primes congruent to 1 modulo 4 dividing n (with multiplicity).

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 2, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 2, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 2, 0, 0, 1, 0, 1, 0, 0, 1, 1, 2, 0, 0, 1, 0, 1, 0, 1, 0, 0, 2, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 2, 1, 1, 0, 1, 1

Offset: 1

Reinhard Zumkeller, Oct 29 2001

David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989, p. 61.

T. D. Noe, Table of n, a(n) for n = 1..10000

First differs from A046080 at n=65.

Cf. A001222, A007814, A027746, A065339 (== 3 (mod 4)), A378879 (=2,3 (mod 4)), A005089 (without multiplicity).

a083025 1 = 0
a083025 n = length [x | x <- a027746_row n, mod x 4 == 1]
-- Reinhard Zumkeller, Jan 10 2012

A083025 := proc(n)
    a := 0 ;
    for f in ifactors(n)[2] do
        if op(1,f) mod 4 = 1 then
            a := a+op(2,f) ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Dec 16 2011

f[n_]:=Plus@@Last/@Select[If[n==1,{},FactorInteger[n]],Mod[#[[1]],4]==1&]; Table[f[n],{n,100}] (* Ray Chandler, Dec 18 2011 *)

A083025(n)=sum(i=1,#n=factor(n)~,if(n[1,i]%4==1,n[2,i]))  \\ M. F. Hasler, Apr 16 2012

a(n) = A001222(n) - A007814(n) - A065339(n).

Totally additive with a(2) = 0, a(p) = 1 if p == 1 (mod 4), and a(p) = 0 if p == 3 (mod 4). - Amiram Eldar, Jun 17 2024

A004144 Nonhypotenuse numbers (indices of positive squares that are not the sums of 2 distinct nonzero squares).

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 16, 18, 19, 21, 22, 23, 24, 27, 28, 31, 32, 33, 36, 38, 42, 43, 44, 46, 47, 48, 49, 54, 56, 57, 59, 62, 63, 64, 66, 67, 69, 71, 72, 76, 77, 79, 81, 83, 84, 86, 88, 92, 93, 94, 96, 98, 99, 103, 107, 108, 112, 114, 118, 121, 124, 126, 127

Offset: 1

N. J. A. Sloane

nonn

Also numbers with no prime factors of form 4*k+1.
m is a term iff A072438(m) = m.
Density 0. - Charles R Greathouse IV, Apr 16 2012
Closed under multiplication. Primitive elements are A045326, 2 and the primes of form 4*k+3. - Jean-Christophe Hervé, Nov 17 2013

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 98-104.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Evan M. Bailey, Table of n, a(n) for n = 1..20000 (Terms 1..1000 from T. D. Noe)
Evan M. Bailey, a004144.cpp.
Steven R. Finch, Landau-Ramanujan Constant [Broken link]
Steven R. Finch, Landau-Ramanujan Constant [From the Wayback machine]
Daniel Shanks, Non-hypotenuse numbers, Fib. Quart., Vol. 13, No. 4 (1975), pp. 319-321.
Eric Weisstein's World of Mathematics, Pythagorean Triple.
Index entries for sequences related to sums of squares.

Complement of A009003.
Cf. A000290, A002145, A005089, A072437, A244659, A244662.
The subsequence of primes is A045326.

import Data.List (elemIndices)
a004144 n = a004144_list !! (n-1)
a004144_list = map (+ 1) $ elemIndices 0 a005089_list
-- Reinhard Zumkeller, Jan 07 2013

fQ[n_] := If[n > 1, First@ Union@ Mod[ First@# & /@ FactorInteger@ n, 4] != 1, True]; Select[ Range@ 127, fQ]
A004144 = Select[Range[127],Length@Reduce[s^2 + t^2 == s # && s > t > 0, Integers] == 0 &] (* Gerry Martens, Jun 09 2020 *)

is(n)=n==1||vecmin(factor(n)[,1]%4)>1 \\ Charles R Greathouse IV, Apr 16 2012

list(lim)=my(v=List(),u=vectorsmall(lim\=1)); forprimestep(p=5,lim,4, forstep(n=p,lim,p, u[n]=1)); for(i=1,lim, if(u[i]==0, listput(v,i))); u=0; Vec(v) \\ Charles R Greathouse IV, Jan 13 2022

A005089(a(n)) = 0. - Reinhard Zumkeller, Jan 07 2013

The number of terms below x is ~ (A * x / sqrt(log(x))) * (1 + C/log(x) + O(1/log(x)^2)), where A = A244659 and C = A244662 (Shanks, 1975). - Amiram Eldar, Jan 29 2022

More terms from Reinhard Zumkeller, Jun 17 2002

Name clarified by Evan M. Bailey, Sep 17 2019

A086275 Number of distinct Gaussian primes in the factorization of n.

Original entry on oeis.org

0, 1, 1, 1, 2, 2, 1, 1, 1, 3, 1, 2, 2, 2, 3, 1, 2, 2, 1, 3, 2, 2, 1, 2, 2, 3, 1, 2, 2, 4, 1, 1, 2, 3, 3, 2, 2, 2, 3, 3, 2, 3, 1, 2, 3, 2, 1, 2, 1, 3, 3, 3, 2, 2, 3, 2, 2, 3, 1, 4, 2, 2, 2, 1, 4, 3, 1, 3, 2, 4, 1, 2, 2, 3, 3, 2, 2, 4, 1, 3, 1, 3, 1, 3, 4, 2, 3, 2, 2, 4, 3, 2, 2, 2, 3, 2, 2, 2, 2, 3

Offset: 1

T. D. Noe, Jul 14 2003

As shown in the formula, a(n) depends on the number of distinct primes of the forms 4*k+1 (A005089) and 4*k-1 (A005091) and whether n is divisible by 2 (A059841).

Note that associated divisors are counted only once. - Jianing Song, Aug 30 2018

			a(1006655265000) = a(2^3*3^2*5^4*7^5*11^3) = 1 + 2*1 + 3 = 6 because n is divisible by 2, has 1 prime factor of the form 4*k+1 and 3 primes of the form 4*k+3. Over the Gaussian integers, 1006655265000 is factored as i*(1 + i)^6*(2 + i)^4*(2 - i)^4*3^2*7^5*11^3, the 6 distinct Gaussian factors are 1 + i, 2 + i, 2 - i, 3, 7 and 11.

T. D. Noe, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Gaussian Prime.

Cf. A005089, A005091, A059841.
Equivalent of arithmetic functions in the ring of Gaussian integers (the corresponding functions in the ring of integers are in the parentheses): A062327 ("d", A000005), A317797 ("sigma", A000203), A079458 ("phi", A000010), A227334 ("psi", A002322), this sequence ("omega", A001221), A078458 ("Omega", A001222), A318608 ("mu", A008683).
Equivalent in the ring of Eisenstein integers: A319443.

Join[{0}, Table[f=FactorInteger[n, GaussianIntegers->True]; cnt=Length[f]; If[MemberQ[{-1, I, -I}, f[[1, 1]]], cnt-- ]; cnt, {n, 2, 100}]]
a[n_]:=If[n==2,1,PrimeNu[n, GaussianIntegers -> True]]; Array[a,100] (* Stefano Spezia, Sep 29 2024 *)

a(n)=my(f=factor(n)[,1]); sum(i=1,#f,if(f[i]%4==1,2,1)) \\ Charles R Greathouse IV, Sep 14 2015

a(n) = A059841(n) + 2*A005089(n) + A005091(n).

Additive with a(p^e) = 2 if p = 1 (mod 4), 1 otherwise. - Franklin T. Adams-Watters, Oct 18 2006

A005091 Number of distinct primes = 3 mod 4 dividing n.

Original entry on oeis.org

0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 2, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 2, 0, 1, 1, 0, 1, 1, 0, 0, 2, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 2, 0, 1, 1, 0, 1, 2, 0, 0, 2, 1, 0, 2, 1, 1, 1, 0, 0, 1, 1, 2, 1, 1, 0, 1, 0, 1, 2, 0, 1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 1, 0, 1, 2, 0, 0, 1

Offset: 1

N. J. A. Sloane

nonn

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Étienne Fouvry and Peter Koymans, On Dirichlet biquadratic fields, arXiv:2001.05350 [math.NT], 2020.

Cf. A001221, A005089, A005094.

Cf. A079261, A027748, A072437, A187811.

a005091 = sum . map a079261 . a027748_row
-- Reinhard Zumkeller, Jan 07 2013

[0] cat [#[p:p in PrimeDivisors(n)| p mod 4 eq 3]: n in [2..100]]; // Marius A. Burtea, Nov 19 2019

[0] cat [&+[Binomial(p,3) mod 2:p in PrimeDivisors(n)]:n in [2..100]]; // Marius A. Burtea, Nov 19 2019

with(numtheory): seq(add(binomial(p,3) mod 2, p in factorset(n)), n=1..100); # Ridouane Oudra, Nov 19 2019

f[n_]:=Length@Select[If[n==1,{},FactorInteger[n]],Mod[#[[1]],4]==3&]; Table[f[n],{n,102}] (* Ray Chandler, Dec 18 2011 *)

for(n=1,100,print1(sumdiv(n,d,isprime(d)*if((d-3)%4,0,1)),","))

from sympy import primefactors
def A005091(n): return sum(1 for p in primefactors(n) if p&3==3) # Chai Wah Wu, Jul 07 2024

Additive with a(p^e) = 1 if p = 3 (mod 4), 0 otherwise.
From Reinhard Zumkeller, Jan 07 2013: (Start)
a(n) = Sum_{k=1..A001221(n)} A079261(A027748(n,k)).
a(A072437(n)) = 0.
a(A187811(n)) > 0. (End)
a(n) = Sum_{p|n} (binomial(p,3) mod 2), where p is a prime. - Ridouane Oudra, Nov 19 2019

cp's OEIS Frontend

A001221 Number of distinct primes dividing n (also called omega(n)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Julia

Magma

Maple

Mathematica

MuPAD

MuPAD

PARI

Python

Sage

SageMath

SageMath

Formula

A009003 Hypotenuse numbers (squares are sums of 2 nonzero squares).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A083025 Number of primes congruent to 1 modulo 4 dividing n (with multiplicity).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A004144 Nonhypotenuse numbers (indices of positive squares that are not the sums of 2 distinct nonzero squares).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Formula

Extensions

A086275 Number of distinct Gaussian primes in the factorization of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A078613 Same numbers of distinct prime factors of forms 4k+1 and 4k+3.

A221264 Numbers having fewer distinct prime factors of form 4k+1 than of 4k+3.

A221265 Numbers having more distinct prime factors of form 4k+1 than of 4k+3.