A066247 -id:A066247 - cp's OEIS frontend

A002808 The composite numbers: numbers n of the form x*y for x > 1 and y > 1.

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88

Offset: 1

N. J. A. Sloane

The natural numbers 1,2,... are divided into three sets: 1 (the unit), the primes (A000040) and the composite numbers (A002808).
The number of composite numbers <= n (A065855) = n - pi(n) (A000720) - 1.
n is composite iff sigma(n) + phi(n) > 2n. This is a nice result of the well known theorem: For all positive integers n, n = Sum_{d|n} phi(d). For the proof see my contribution to puzzle 76 of Carlos Rivera's Primepuzzles. - Farideh Firoozbakht, Jan 27 2005, Jan 18 2015
The composite numbers have the semiprimes A001358 as primitive elements.
A211110(a(n)) > 1. - Reinhard Zumkeller, Apr 02 2012
A060448(a(n)) > 1. - Reinhard Zumkeller, Apr 05 2012
A086971(a(n)) > 0. - Reinhard Zumkeller, Dec 14 2012
Composite numbers n which are the product of r=A001222(n) prime numbers are sometimes called r-almost primes. Sequences listing r-almost primes are: A000040 (r = 1), A001358 (r = 2), A014612 (r = 3), A014613 (r = 4), A014614 (r = 5), A046306 (r = 6), A046308 (r = 7), A046310 (r = 8), A046312 (r = 9), A046314 (r = 10), A069272 (r = 11), A069273 (r = 12), A069274 (r = 13), A069275 (r = 14), A069276 (r = 15), A069277 (r = 16), A069278 (r = 17), A069279 (r = 18), A069280 (r = 19), A069281 (r = 20). - Jason Kimberley, Oct 02 2011
a(n) = A056608(n) * A160180(n). - Reinhard Zumkeller, Mar 29 2014
Degrees for which there are irreducible polynomials which are reducible mod p for all primes p, see Brandl. - Charles R Greathouse IV, Sep 04 2014
An integer is composite if and only if it is the sum of strictly positive integers in arithmetic progression with common difference 2: 4 = 1 + 3, 6 = 2 + 4, 8 = 3 + 5, 9 = 1 + 3 + 5, etc. - Jean-Christophe Hervé, Oct 02 2014
This statement holds since k+(k+2)+...+k+2(n-1) = n*(n+k-1) = a*b with arbitrary a,b (taking n=a and k=b-a+1 if b>=a). - M. F. Hasler, Oct 04 2014
For n > 4, these are numbers n such that n!/n^2 = (n-1)!/n is an integer (see A056653). - Derek Orr, Apr 16 2015
Let f(x) = Sum_{i=1..x} Sum_{j=2..i-1} cos((2*Pi*x*j)/i). It is known that the zeros of f(x) are the prime numbers. So these are the numbers n such that f(n) > 0. - Michel Lagneau, Oct 13 2015
Numbers n that can be written as solutions of the Diophantine equation n = (x+2)(y+2) where {x,y} in N^2, pairs of natural numbers including zero (cf. Mathematica code and Davis). - Ron R Spencer and Bradley Klee, Aug 15 2016
Numbers n with a partition (containing at least two summands) so that its summands also multiply to n. If n is prime, there is no way to find those two (or more) summands. If n is composite, simply take a factor or several, write those divisors and fill with enough 1's so that they add up to n. For example: 4 = 2*2 = 2+2, 6 = 1*2*3 = 1+2+3, 8 = 1*1*2*4 = 1+1+2+4, 9 = 1*1*1*3*3 = 1+1+1+3+3. - Juhani Heino, Aug 02 2017

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 2.
A. E. Bojarincev, Asymptotic expressions for the n-th composite number, Univ. Mat. Zap. 6:21-43 (1967). - In Russian.
John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 127.
Martin Davis, "Algorithms, Equations, and Logic", pp. 4-15 of S. Barry Cooper and Andrew Hodges, Eds., "The Once and Future Turing: Computing the World", Cambridge 2016.
R. K. Guy, Unsolved Problems Number Theory, Section A.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 2.
D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 66.
Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 51.
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, Table of n, a(n) for n = 1..17737 [composites up to 20000]
Rolf Brandl, Integer polynomials that are reducible modulo all primes, Amer. Math. Monthly 93 (1986), pp. 286-288.
C. K. Caldwell, Composite Numbers
Felix Huber, Illustration for a(1)-a(12)
Laurentiu Panaitopol, Some properties of the series of composed [sic] numbers, Journal of Inequalities in Pure and Applied Mathematics 2:3 (2001).
Carlos Rivera, Puzzle 76, z(n)=sigma(n) + phi(n) - 2n, The Prime Puzzles and Problems Connection.
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 1962 64-94
Eric Weisstein's World of Mathematics, Composite Number
Index entries for "core" sequences
Index entries for sequences from "Goedel, Escher, Bach"

Complement of A008578. - Omar E. Pol, Dec 16 2016
Cf. A000040, A018252, A065090, A136527.
Cf. A073783 (first differences), A073445 (second differences).
Boustrophedon transforms: A230954, A230955.
Cf. A163870 (nontrivial divisors).
Related sequences:
Primes (p) and composites (c): A000040, A002808, A000720, A065855.
Primes between p(n) and 2*p(n): A063124, A070046; between c(n) and 2*c(n): A376761; between n and 2*n: A035250, A060715, A077463, A108954.
Composites between p(n) and 2*p(n): A246514; between c(n) and 2*c(n): A376760; between n and 2*n: A075084, A307912, A307989, A376759.

a002808 n = a002808_list !! (n-1)
a002808_list = filter ((== 1) . a066247) [2..]
-- Reinhard Zumkeller, Feb 04 2012

[n: n in [2..250] | not IsPrime(n)]; // G. C. Greubel, Feb 24 2024

t := []: for n from 2 to 20000 do if isprime(n) then else t := [op(t),n]; fi; od: t; remove(isprime,[$3..89]); # Zerinvary Lajos, Mar 19 2007
A002808 := proc(n) option remember ; local a ; if n = 1 then 4; else for a from procname(n-1)+1 do if not isprime(a) then return a; end if; end do ; end if; end proc; # R. J. Mathar, Oct 27 2009

Select[Range[2,100], !PrimeQ[#]&] (* Zak Seidov, Mar 05 2011 *)
With[{nn=100},Complement[Range[nn],Prime[Range[PrimePi[nn]]]]] (* Harvey P. Dale, May 01 2012 *)
Select[Range[100], CompositeQ] (* Jean-François Alcover, Nov 07 2021 *)

A002808(n)=for(k=0,primepi(n),isprime(n++)&&k--);n \\ For illustration only: see below. - M. F. Hasler, Oct 31 2008

A002808(n)= my(k=-1); while(-n + n += -k + k=primepi(n),); n \\ For n=10^4 resp. 3*10^4, this is about 100 resp. 500 times faster than the former; M. F. Hasler, Nov 11 2009

forcomposite(n=1, 1e2, print1(n, ", ")) \\ Felix Fröhlich, Aug 03 2014

for(n=1, 1e3, if(bigomega(n) > 1, print1(n, ", "))) \\ Altug Alkan, Oct 14 2015

from sympy import primepi
def A002808(n):
    m, k = n, primepi(n) + 1 + n
    while m != k:
        m, k = k, primepi(k) + 1 + n
    return m # Chai Wah Wu, Jul 15 2015, updated Apr 14 2016

from sympy import isprime
def ok(n): return n > 1 and not isprime(n)
print([k for k in range(89) if ok(k)]) # Michael S. Branicky, Nov 07 2021

next_A002808=lambda n: next(n for n in range(n,n*5)if not isprime(n)) # next composite >= n > 0; next_A002808(n)==n <=> iscomposite(n). - M. F. Hasler, Mar 28 2025
is_A002808=lambda n:not isprime(n) and n>1 # where isprime(n) can be replaced with: all(n%d for d in range(2, int(n**.5)+1))
# generators of composite numbers:
A002808_upto=lambda stop=1<<59: filter(is_A002808, range(2,stop))
A002808_seq=lambda:(q:=2)and(n for p in primes if (o:=q)<(q:=p) for n in range(o+1,p)) # with, e.g.: primes=filter(isprime,range(2,1<<59)) # M. F. Hasler, Mar 28 2025

[n for n in (2..250) if not is_prime(n)] # G. C. Greubel, Feb 24 2024

a(n) = pi(a(n)) + 1 + n, where pi is the prime counting function.
a(n) = A136527(n, n).
A000005(a(n)) > 2. - Juri-Stepan Gerasimov, Oct 17 2009
A001222(a(n)) > 1. - Juri-Stepan Gerasimov, Oct 30 2009
A000203(a(n)) < A007955(a(n)). - Juri-Stepan Gerasimov, Mar 17 2011
A066247(a(n)) = 1. - Reinhard Zumkeller, Feb 05 2012
Sum_{n>=1} 1/a(n)^s = Zeta(s)-1-P(s), where P is prime zeta. - Enrique Pérez Herrero, Aug 08 2012
n + n/log n + n/log^2 n < a(n) < n + n/log n + 3n/log^2 n for n >= 4, see Panaitopol. Bojarincev gives an asymptotic version. - Charles R Greathouse IV, Oct 23 2012
a(n) > n + A000720(n) + 1. - François Huppé, Jan 08 2025

Deleted an incomplete and broken link. - N. J. A. Sloane, Dec 16 2010

A006753 Smith (or joke) numbers: composite numbers k such that sum of digits of k = sum of digits of prime factors of k (counted with multiplicity).

Original entry on oeis.org

4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438, 454, 483, 517, 526, 535, 562, 576, 588, 627, 634, 636, 645, 648, 654, 663, 666, 690, 706, 728, 729, 762, 778, 825, 852, 861, 895, 913, 915, 922, 958, 985, 1086, 1111, 1165, 1219

Offset: 1

N. J. A. Sloane

Of course primes also have this property, trivially.
a(133809) = 4937775 is the first Smith number historically: 4937775 = 3*5*5*65837 and 4+9+3+7+7+7+5 = 3+5+5+(6+5+8+3+7) = 42, Albert Wilansky coined the term Smith number when he noticed the defining property in the phone number of his brother-in-law Harold Smith: 493-7775.
There are 248483 7-digit Smith numbers, corresponding to US phone numbers without area codes (like 4937775). - Charles R Greathouse IV, May 19 2013
A007953(a(n)) = Sum_{k=1..A001222(a(n))} A007953(A027746(a(n),k)), and A066247(a(n))=1. - Reinhard Zumkeller, Dec 19 2011
3^3, 3^6, 3^9, 3^27 are in the sequence. - Sergey Pavlov, Apr 01 2017
As mentioned by Giovanni Resta, there are no other terms of the form 3^t for 0 < t < 300000 and, probably, no other terms of such form for t >= 300000. It seems that, if there exists any other term of form 3^t with integer t, then t == 0 (mod 3) or, perhaps, t = {3^k; 2*3^k} where k is an integer, k > 10. - Sergey Pavlov, Apr 03 2017

			58 = 2*29; sum of digits of 58 is 13, sum of digits of 2 + sum of digits of 29 = 2+11 is also 13.

M. Gardner, Penrose Tiles to Trapdoor Ciphers. Freeman, NY, 1989, p. 300.
R. K. Guy, Unsolved Problems in the Theory of Numbers, Section B49.
C. A. Pickover, "A Brief History of Smith Numbers" in "Wonders of Numbers: Adventures in Mathematics, Mind and Meaning", pp. 247-248, Oxford University Press, 2000.
J. E. Roberts, Lure of the Integers, pp. 269-270 MAA 1992.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
D. D. Spencer, Key Dates in Number Theory History, Camelot Pub. Co. FL, 1995, pp. 94.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, Exercise 3.1.14 and 3.1.16 on pages 84-85.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers (Rev. ed. 1997), p. 180.

T. D. Noe, Table of n, a(n) for n = 1..10000
K. S. Brown's Mathpages, Smith Numbers and Rhonda Numbers
C. K. Caldwell, The Prime Glossary, Smith number
P. J. Costello, Smith Numbers
M. Gardner, Letter to N. J. A. Sloane, Jun 20 1991.
Ely Golden, General program for generating Smith number sequences
S. S. Gupta, Smith Numbers
T. Jason, Smith number
Madras Math's Amazing Number Facts, Smith Numbers.
Wayne L. McDaniel, The Existence of Infinitely Many k-Smith Numbers, The Fibonacci Quarterly, 25(1), 76-80, (1987).
Sham Oltikar, and Keith Wayland, Construction of Smith Numbers, Mathematics Magazine, vol. 56(1), 1983, pp. 36-37.
C. A. Pickover, "Wonders of Numbers, Adventures in Mathematics, Mind and Meaning," Zentralblatt review
Carlos Rivera, Problem 107: Consecutive Smith numbers, The Prime Puzzles and Problems Connection.
Carlos Rivera, Problem 108: Methods for generating Smith numbers, The Prime Puzzles and Problems Connection.
W. Schneider, Smith Numbers
Eric Weisstein's World of Mathematics, Smith Number
Wikipedia, Smith number
A. Wilansky, Smith numbers, Two-Year Coll. Math. J., 13 (1982), p. 21.
A. Witno, A Family of Sequences Generating Smith Numbers, J. Int. Seq. 16 (2013) #13.4.6

Cf. A002808, A007953, A019506, A050218, A050224, A050255, A098834-A098840, A103123-A103126, A104166-A104171, A104390, A104391, A202387, A202388.

a006753 n = a006753_list !! (n-1)
a006753_list = [x | x <- a002808_list,
                    a007953 x == sum (map a007953 (a027746_row x))]
-- Reinhard Zumkeller, Dec 19 2011

q:= n-> not isprime(n) and (s-> s(n)=add(s(i[1])*i[2], i=
     ifactors(n)[2]))(h-> add(i, i=convert(h, base, 10))):
select(q, [$1..2000])[];  # Alois P. Heinz, Apr 22 2021

fQ[n_] := !PrimeQ@ n && n>1 && Plus @@ Flatten[ IntegerDigits@ Table[ #[[1]], {#[[2]] }] & /@ FactorInteger@ n] == Plus @@ IntegerDigits@ n; Select[ Range@ 1200, fQ]

isA006753(n) = if(isprime(n), 0, my(f=factor(n)); sum(i=1,#f[,1], sumdigits(f[i,1])*f[i,2]) == sumdigits(n)); \\ Charles R Greathouse IV, Jan 03 2012; updated by Max Alekseyev, Oct 21 2016

from sympy import factorint
def sd(n): return sum(map(int, str(n)))
def ok(n):
  f = factorint(n)
  return sum(f[p] for p in f) > 1 and sd(n) == sum(sd(p)*f[p] for p in f)
print(list(filter(ok, range(1220)))) # Michael S. Branicky, Apr 22 2021

is_A006753 = lambda n: n > 1 and not is_prime(n) and sum(n.digits()) == sum(sum(p.digits())*m for p,m in factor(n)) # D. S. McNeil, Dec 28 2010

A065855 Number of composites <= n.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 2, 3, 4, 5, 5, 6, 6, 7, 8, 9, 9, 10, 10, 11, 12, 13, 13, 14, 15, 16, 17, 18, 18, 19, 19, 20, 21, 22, 23, 24, 24, 25, 26, 27, 27, 28, 28, 29, 30, 31, 31, 32, 33, 34, 35, 36, 36, 37, 38, 39, 40, 41, 41, 42, 42, 43, 44, 45, 46, 47, 47, 48, 49, 50, 50, 51, 51, 52, 53

Offset: 1

Labos Elemer, Nov 26 2001

Also number of primes between prime(n) and n. - Joseph L. Pe, Sep 24 2002
Plot the points (n,a(n)) by, say, appending the line ListPlot[%, PlotJoined -> True] to the Mathematica program. The result is virtually a straight line passing through the origin. For the first thousand points, the slope is approximately = 3/4. (This behavior can be explained by using the prime number theorem.) - Joseph L. Pe, Sep 24 2002
Partial sums of A066247, the characteristic function of composites. - Reinhard Zumkeller, Oct 14 2014
Appears to be the same as the coefficient h*1 of the h* polynomial for polytope representing the number n. See Ya-Ping Lu and Shu-Fang Deng (2020), Table 3.1. - _N. J. A. Sloane, Mar 26 2020

			Prime(8) = 19 and there are 3 primes between 8 and 19 (endpoints are excluded), namely 11, 13, 17. Hence a(8) = 3.

N. J. A. Sloane, Table of n, a(n) for n = 1..20000 [First 1000 terms from T. D. Noe]
Ya-Ping Lu and Shu-Fang Deng, Properties of Polytopes Representing Natural Numbers, arXiv:2003.08968 [math.GM], 2020.

Cf. A000720, A062298, A002808.
Cf. A066247.
Related sequences:
Primes (p) and composites (c): A000040, A002808, A000720, A065855.
Primes between p(n) and 2*p(n): A063124, A070046; between c(n) and 2*c(n): A376761; between n and 2*n: A035250, A060715, A077463, A108954.
Composites between p(n) and 2*p(n): A246514; between c(n) and 2*c(n): A376760; between n and 2*n: A075084, A307912, A307989, A376759.

a065855 n = a065855_list !! (n-1)
a065855_list = scanl1 (+) (map a066247 [1..])
-- Reinhard Zumkeller, Oct 20 2014

A065855 := proc(n) if n <= 3 then 0 else n - numtheory:-pi(n) - 1; fi; end; # N. J. A. Sloane, Oct 20 2024
a := [seq(A065855(n),n=1..120)];

(*gives number of primes < n*) f[n_] := Module[{r, i}, r = 0; i = 1; While[Prime[i] < n, i++ ]; i - 1]; (*gives number of primes between m and n with endpoints excluded*) g[m_, n_] := Module[{r}, r = f[m] - f[n]; If[PrimeQ[n], r = r - 1]; r]; Table[g[Prime[n], n], {n, 1, 1000}]
Table[n-PrimePi[n]-1,{n,75}] (* Harvey P. Dale, Jun 14 2011 *)
Accumulate[Table[If[CompositeQ[n],1,0],{n,100}]] (* Harvey P. Dale, Sep 24 2016 *)

a(n) = { n - primepi(n) - 1 } \\ Harry J. Smith, Nov 01 2009

from sympy import primepi
def A065855(n):
    return 0 if n < 4 else n - primepi(n) - 1 # Chai Wah Wu, Apr 14 2016

a(n) = n - A000720(n) - 1 = A062298(n) - 1.

A091247 Characteristic function of A091242: 1 if the n-th GF(2)[X] polynomial is reducible, 0 otherwise.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1

Offset: 0

Antti Karttunen, Jan 03 2004

nonn

Antti Karttunen, Table of n, a(n) for n = 0..65537
A. Karttunen, Scheme-program for computing this sequence.
Index entries for characteristic functions
Index entries for sequences operating on GF(2)[X]-polynomials

Cf. A066247, A091203, A091205, A091246.

Complementary to A091225. Partial sums give A091245.

a(n) = if (n<2, 0, ! polisirreducible(Mod(1,2)*Pol(binary(n)))); \\ Michel Marcus, Apr 12 2015

a(n) = A066247(A091203(n)) = A066247(A091205(n)).

A086971 Number of semiprime divisors of n.

Original entry on oeis.org

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

Offset: 1

Reinhard Zumkeller, Sep 22 2003

nonn

Inverse Moebius transform of A064911. - Jonathan Vos Post, Dec 08 2004

G. H. Hardy and E. M. Wright, Section 17.10 in An Introduction to the Theory of Numbers, 5th ed., Oxford, England: Clarendon Press, 1979.

T. D. Noe, Table of n, a(n) for n = 1..10000
E. A. Bender and J. R. Goldman, On the Applications of Mobius Inversion in Combinatorial Analysis, Amer. Math. Monthly 82, (1975), 789-803.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
N. J. A. Sloane, Transforms.
Eric Weisstein's World of Mathematics, Semiprime.
Eric Weisstein's World of Mathematics, Divisor Function.
Eric Weisstein's World of Mathematics, Moebius Transform.

Cf. A001358, A064911, A001221, A000005, A000010, A004018, A007913, A056170, A079275, A001222, A220264 (least inverse).

a086971 = sum . map a064911 . a027750_row
-- Reinhard Zumkeller, Dec 14 2012

a:= proc(n) local l, m; l:=ifactors(n)[2]; m:=nops(l);
       m*(m-1)/2 +add(`if`(i[2]>1, 1, 0), i=l)
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Jul 18 2013

semiPrimeQ[n_] := PrimeOmega@ n == 2; f[n_] := Length@ Select[Divisors@ n, semiPrimeQ@# &]; Array[f, 105] (* Zak Seidov, Mar 31 2011 and modified by Robert G. Wilson v, Dec 08 2012 *)
a[n_] := Count[e = FactorInteger[n][[;; , 2]], ?(# > 1 &)] + (o = Length[e])*(o - 1)/2; Array[a, 100] (* _Amiram Eldar, Jun 30 2022 *)

/* The following definitions of a(n) are equivalent. */
a(n) = sumdiv(n,d,bigomega(d)==2)
a(n) = f=factor(n); j=matsize(f)[1]; sum(m=1,j,f[m,2]>=2) + binomial(j,2)
a(n) = f=factor(n); j=omega(n); sum(m=1,j,f[m,2]>=2) + binomial(j,2)
a(n) = omega(n/core(n)) + binomial(omega(n),2)
/* Rick L. Shepherd, Mar 06 2006 */

a(n) = A106404(n) + A106405(n). - Reinhard Zumkeller, May 02 2005
a(n) = omega(n/core(n)) + binomial(omega(n),2) = A001221(n/A007913(n)) + binomial(A001221(n),2) = A056170(n) + A079275(n). - Rick L. Shepherd, Mar 06 2006
From Reinhard Zumkeller, Dec 14 2012: (Start)
a(n) = Sum_{k=1..A000005(n)} A064911(A027750(n,k)).
a(A220264(n)) = n and a(m) <> n for m < A220264(n); a(A008578(n)) = 0; a(A002808(n)) > 0; for n > 1: a(A102466(n)) <= 1 and a(A102467(n)) > 1; A066247(n) = A057427(a(n)). (End)
G.f.: Sum_{k = p*q, p prime, q prime} x^k/(1 - x^k). - Ilya Gutkovskiy, Jan 25 2017

Entry revised by N. J. A. Sloane, Mar 28 2006

A091203 Factorization-preserving isomorphism from binary codes of GF(2) polynomials to integers.

Original entry on oeis.org

0, 1, 2, 3, 4, 9, 6, 5, 8, 15, 18, 7, 12, 11, 10, 27, 16, 81, 30, 13, 36, 25, 14, 33, 24, 17, 22, 45, 20, 21, 54, 19, 32, 57, 162, 55, 60, 23, 26, 63, 72, 29, 50, 51, 28, 135, 66, 31, 48, 35, 34, 243, 44, 39, 90, 37, 40, 99, 42, 41, 108, 43, 38, 75, 64, 225, 114, 47, 324

Offset: 0

Antti Karttunen, Jan 03 2004

nonn

E.g. we have the following identities: A000040(n) = a(A014580(n)), A091219(n) = A008683(a(n)), A091220(n) = A000005(a(n)), A091221(n) = A001221(a(n)), A091222(n) = A001222(a(n)), A091225(n) = A010051(a(n)), A091227(n) = A049084(a(n)), A091247(n) = A066247(a(n)).

Antti Karttunen, Table of n, a(n) for n = 0..8192
A. Karttunen, Scheme-program for computing this sequence.
Index entries for sequences operating on GF(2)[X]-polynomials
Index entries for sequences that are permutations of the natural numbers

Inverse: A091202.
Several variants exist: A235042, A091205, A106443, A106445, A106447.
Cf. also A000005, A000040, A001221, A001222, A004247, A008683, A010051, A014580, A048720, A049084, A066247, A091219, A091220, A091221, A091222, A091225, A091227, A091247, A234741, A234742, A245703, A245704, A278233.
Cf. also A302024, A302026, A305418, A305428 for other similar permutations.

A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From A003961
A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
A305419(n) = if(n<3,1, my(k=n-1); while(k>1 && !A091225(k),k--); (k));
A305422(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305419(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
A091203(n) = if(n<=1,n,if(!(n%2),2*A091203(n/2),A003961(A091203(A305422(n))))); \\ Antti Karttunen, Jun 10 2018

a(0)=0, a(1)=1. For n's coding an irreducible polynomial ir_i, that is if n=A014580(i), we have a(n) = A000040(i) and for composite polynomials a(ir_i X ir_j X ...) = p_i * p_j * ..., where p_i = A000040(i) and X stands for carryless multiplication of GF(2)[X] polynomials (A048720) and * for the ordinary multiplication of integers (A004247).
Other identities. For all n >= 1, the following holds:
A010051(a(n)) = A091225(n). [After a(1)=1, maps binary representations of irreducible GF(2) polynomials, A014580, to primes and the binary representations of corresponding reducible polynomials, A091242, to composite numbers. The permutations A091205, A106443, A106445, A106447, A235042 and A245704 have the same property.]
From Antti Karttunen, Jun 10 2018: (Start)
For n <= 1, a(n) = n, for n > 1, a(n) = 2*a(n/2) if n is even, and if n is odd, then a(n) = A003961(a(A305422(n))).
a(n) = A005940(1+A305418(n)) = A163511(A305428(n)).
A046523(a(n)) = A278233(n).
(End)

A019506 Hoax numbers: composite numbers whose digit-sum equals the sum of the digit-sums of its distinct prime factors.

Original entry on oeis.org

22, 58, 84, 85, 94, 136, 160, 166, 202, 234, 250, 265, 274, 308, 319, 336, 346, 355, 361, 364, 382, 391, 424, 438, 454, 456, 476, 483, 516, 517, 526, 535, 562, 627, 634, 644, 645, 650, 654, 660, 663, 690, 702, 706, 732, 735, 762, 778, 855, 860

Offset: 1

Mario Velucchi (mathchess(AT)velucchi.it)

			22 = 2*11 and digit-sum(22) = 4 = digit-sum(2) + digit-sum(11).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Shyam Sunder Gupta, Smith Numbers, Exploring the Beauty of Fascinating Numbers, Springer (2025) Ch. 4, 127-157.
Eric Weisstein's World of Mathematics, Hoax Number

Cf. A006753.

Cf. A002808, A027748, A001221, A007953, A050223, A202393, A202387.

a019506 n = a019506_list !! (n-1)
a019506_list = [x | x <- a002808_list,
                    a007953 x == sum (map a007953 (a027748_row x))]
-- Reinhard Zumkeller, Dec 19 2011

Select[Range[2,1000],!PrimeQ[#]&&Total[Flatten[IntegerDigits/@ Transpose[ FactorInteger[#]][[1]]]]==Total[IntegerDigits[#]]&] (* Harvey P. Dale, Feb 24 2013 *)

isok(m) = !isprime(m) && (sumdigits(m) == vecsum(apply(sumdigits, factor(m)[,1]))); \\ Michel Marcus, Feb 03 2022

A007953(a(n)) = sum(A007953(A027748(a(n),k)): k=1..A001221(a(n))) and A066247(a(n)) = 1. [Reinhard Zumkeller, Dec 19 2011]

A235042 Factorization-preserving bijection from GF(2)[X]-polynomials to nonnegative integers, version which fixes the elements that are irreducible in both semirings.

Original entry on oeis.org

0, 1, 2, 3, 4, 9, 6, 7, 8, 21, 18, 11, 12, 13, 14, 27, 16, 81, 42, 19, 36, 49, 22, 39, 24, 5, 26, 63, 28, 33, 54, 31, 32, 93, 162, 91, 84, 37, 38, 99, 72, 41, 98, 15, 44, 189, 78, 47, 48, 77, 10, 243, 52, 57, 126, 17, 56, 117, 66, 59, 108, 61, 62, 147, 64, 441

Offset: 0

Antti Karttunen, Jan 02 2014

nonn

Like A091203 this is a factorization-preserving isomorphism from GF(2)[X]-polynomials to integers. The former are encoded in the binary representation of n like this: n=11, '1011' in binary, stands for polynomial x^3+x+1, n=25, '11001' in binary, stands for polynomial x^4+x^3+1. However, this version does not map the irreducible GF(2)[X] polynomials (A014580) straight to the primes (A000040), but instead fixes the intersection of those two sets (A091206), and maps the elements in their set-wise difference A014580 \ A000040 (= A091214) in numerical order to the set-wise difference A000040 \ A014580 (= A091209).
The composite values are defined by the multiplicativity. E.g., we have a(A048724(n)) = 3*a(n) and a(A001317(n)) = A000244(n) = 3^n for all n.
This map satisfies many of the same identities as A091203, e.g., we have A091219(n) = A008683(a(n)), A091220(n) = A000005(a(n)), A091221(n) = A001221(a(n)), A091222(n) = A001222(a(n)), A091225(n) = A010051(a(n)) and A091247(n) = A066247(a(n)) for all n >= 1.

			Here (t X u) = A048720(t,u):
a(2)=2, a(3)=3 and a(7)=7, as 2, 3 and 7 are all in A091206.
a(4) = a(2 X 2) = a(2)*a(2) = 2*2 = 4.
a(5) = a(3 X 3) = a(3)*a(3) = 3*3 = 9.
a(9) = a(3 X 7) = a(3)*a(7) = 3*7 = 21.
a(10) = a(2 X 3 X 3) = a(2)*a(3)*a(3) = 2*3*3 = 18.
a(15) = a(3 X 3 X 3) = a(3)^3 = 3^3 = 27.
a(17) = a(3 X 3 X 3 X 3) = a(3)^4 = 3^4 = 81.
a(21) = a(7 X 7) = a(7)*a(7) = 7*7 = 49.
a(25) = 5, as 25 is the first term of A091214 and 5 is the first term of A091209.
a(50) = a(2 X 25) = a(2)*a(25) = 2*5 = 10.

Inverse: A235041. Fixed points: A235045.
Cf. A010051, A004247, A091225, A091209, A235044.
Similar cross-multiplicative permutations: A091203, A091205, A106443, A106445, A106447.

a(0)=0, a(1)=1, a(p) = p for those irreducible GF(2)[X]-polynomials whose binary encoding is a prime (i.e., p is in A091206), and for the rest of irreducible GF(2)[X]-polynomials (those which are encoded by a composite natural number, i.e., q is in A091214), a(q) = A091209(A235044(q)), and for reducible polynomials, a(i X j X k X ...) = a(i) * a(j) * a(k) * ..., where each i, j, k, ... is in A014580, X stands for carryless multiplication of GF(2)[X] polynomials (A048720) and * for the ordinary multiplication of integers (A004247).

A379301 Positive integers whose prime indices include a unique composite number.

Original entry on oeis.org

7, 13, 14, 19, 21, 23, 26, 28, 29, 35, 37, 38, 39, 42, 43, 46, 47, 52, 53, 56, 57, 58, 61, 63, 65, 69, 70, 71, 73, 74, 76, 77, 78, 79, 84, 86, 87, 89, 92, 94, 95, 97, 101, 103, 104, 105, 106, 107, 111, 112, 113, 114, 115, 116, 117, 119, 122, 126, 129, 130, 131

Offset: 1

Gus Wiseman, Dec 25 2024

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The prime indices of 70 are {1,3,4}, so 70 is in the sequence.
The prime indices of 98 are {1,4,4}, so 98 is not in the sequence.

For no composite parts we have A302540, counted by A034891 (strict A036497).
For all composite parts we have A320629, counted by A023895 (strict A204389).
For a unique prime part we have A331915, counted by A379304 (strict A379305).
Positions of one in A379300.
Partitions of this type are counted by A379302 (strict A379303).
A000040 lists the prime numbers, differences A001223.
A002808 lists the composite numbers, nonprimes A018252, differences A073783 or A065310.
A055396 gives least prime index, greatest A061395.
A056239 adds up prime indices, row sums of A112798, counted by A001222.
A066247 is the characteristic function for the composite numbers.
A377033 gives k-th differences of composite numbers, see A073445, A377034-A377037.
Other counts of prime indices:
- A087436 postpositive, see A038550.
- A257991 odd, see A000041, A000070, A066207, A349158.
- A257992 even, see A000009, A038348, A066208, A379317.
- A257994 prime, see A000586, A000607, A076610, A331386.
- A330944 nonprime, see A002095, A096258, A320628, A330945.
- A379306 squarefree, see A302478, A379308, A379309, A379316.
- A379310 nonsquarefree, see A114374, A256012, A379307.
- A379311 old prime, see A379312-A379315.
Cf. A113646, A376680.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Length[Select[prix[#],CompositeQ]]==1&]

cp's OEIS Frontend

A143962 Binomial transform of A066247 (characteristic function of composite numbers).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A002808 The composite numbers: numbers n of the form x*y for x > 1 and y > 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Python

SageMath

Formula

Extensions

A006753 Smith (or joke) numbers: composite numbers k such that sum of digits of k = sum of digits of prime factors of k (counted with multiplicity).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Sage

A065855 Number of composites <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A091247 Characteristic function of A091242: 1 if the n-th GF(2)[X] polynomial is reducible, 0 otherwise.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A086971 Number of semiprime divisors of n.

Views

Author

Keywords

Comments