A036234 -id:A036234 - cp's OEIS frontend

A187106 Number of nonempty subsets of {1, 2, ..., n} having pairwise coprime elements.

1, 3, 7, 11, 23, 27, 55, 71, 103, 115, 231, 247, 495, 543, 615, 727, 1455, 1519, 3039, 3231, 3615, 3871, 7743, 7999, 11167, 11903, 14655, 15487, 30975, 31231, 62463, 69887, 76159, 80255, 89855, 91647, 183295, 192639, 208639, 214271, 428543

Offset: 1

Alois P. Heinz, Mar 06 2011

nonn

			a(4) = 11 because there are 11 nonempty subsets of {1,2,3,4} having pairwise coprime elements: {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {3,4}, {1,2,3}, {1,3,4}.

Alois P. Heinz, Table of n, a(n) for n = 1..220

Cf. A036234. Row sums of triangle A186974. Partial sums of A186973. Rightmost elements in rows of triangle A187262.

Cf. A084422.

f(n,k=1)=if(n==1, return(2)); if(gcd(k,n)==1, f(n-1,n*k)) + f(n-1,k)
a(n)=f(n)-1 \\ Charles R Greathouse IV, Aug 24 2016

a(n) = Sum_{k=1..A036234(n)} A186974(n,k).
a(n) = Sum_{i=1..n} A186973(i).
a(n) = A187262(n,A036234(n)).
a(n) = A084422(n) - 1.

A356068 Number of integers ranging from 1 to n that are not prime-powers (1 is not a prime-power).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6, 7, 7, 8, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 14, 15, 16, 17, 18, 18, 19, 20, 21, 21, 22, 22, 23, 24, 25, 25, 26, 26, 27, 28, 29, 29, 30, 31, 32, 33, 34, 34, 35, 35, 36, 37, 37, 38, 39, 39, 40, 41, 42

Offset: 1

Gus Wiseman, Jul 31 2022

nonn

			The a(30) = 14 numbers: 1, 6, 10, 12, 14, 15, 18, 20, 21, 22, 24, 26, 28, 30.

The complement is counted by A025528, with 1's A065515.
For primes instead of prime-powers we have A062298, with 1's A065855.
The version treating 1 as a prime-power is A085970.
One more than the partial sums of A143731.
A000688 counts factorizations into prime-powers.
A001222 counts prime-power divisors.
A246655 lists the prime-powers (A000961 includes 1), towers A164336.
Cf. A000720, A023894, A036234, A050361, A054685, A069513, A355743, A356064, A356065, A356066.

Table[Length[Select[Range[n],!PrimePowerQ[#]&]],{n,100}]

a(n) = A085970(n) + 1.

A379311 Number of prime indices of n that are 1 or prime.

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 0, 3, 2, 2, 1, 3, 0, 1, 2, 4, 1, 3, 0, 3, 1, 2, 0, 4, 2, 1, 3, 2, 0, 3, 1, 5, 2, 2, 1, 4, 0, 1, 1, 4, 1, 2, 0, 3, 3, 1, 0, 5, 0, 3, 2, 2, 0, 4, 2, 3, 1, 1, 1, 4, 0, 2, 2, 6, 1, 3, 1, 3, 1, 2, 0, 5, 0, 1, 3, 2, 1, 2, 0, 5, 4, 2, 1, 3, 2, 1, 1

Offset: 1

Gus Wiseman, Dec 27 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 39 are {2,6}, so a(39) = 1.
The prime indices of 70 are {1,3,4}, so a(70) = 2.
The prime indices of 98 are {1,4,4}, so a(98) = 1.
The prime indices of 294 are {1,2,4,4}, a(294) = 2.
The prime indices of 1911 are {2,4,4,6}, so a(1911) = 1.
The prime indices of 2548 are {1,1,4,4,6}, so a(2548) = 2.

Positions of first appearances are A000079.
These "old" primes are listed by A008578.
Positions of zero are A320629, counted by A023895 (strict A204389).
Positions of one are A379312, counted by A379314 (strict A379315).
Positions of nonzero terms are A379313.
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.
A080339 is the characteristic function for the old prime numbers.
A376682 gives k-th differences of old prime numbers, see A030016, A075526, A173390, A376683, A376855.
Other counts of prime indices:
- A257991 odd, see A000041, A000070, A066207, A349158.
- A257992 even, see A000009, A038348, A066208, A379317.
- A257994 prime, see A000586, A000607, A076610, A331386, A331915, A379304, A379305.
- A330944 nonprime, see A002095, A096258, A320628, A330945.
- A379306 squarefree, see A302478, A379308, A379309, A379316.
- A379310 nonsquarefree, see A114374, A256012, A379307.
Cf. A034891, A036234, A036497, A038550, A087436, A302540, A379300, A379301.

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

Totally additive with a(prime(k)) = A080339(k).

A186971 Maximal cardinality of a subset of {1, 2, ..., n} containing n and having pairwise coprime elements.

Original entry on oeis.org

1, 2, 3, 3, 4, 3, 5, 5, 5, 4, 6, 5, 7, 6, 6, 7, 8, 7, 9, 8, 8, 8, 10, 9, 10, 9, 10, 9, 11, 9, 12, 12, 11, 11, 11, 11, 13, 12, 12, 12, 14, 12, 15, 14, 14, 14, 16, 15, 16, 15, 15, 15, 17, 16, 16, 16, 16, 16, 18, 16, 19, 18, 18, 19, 18, 17, 20

Offset: 1

Alois P. Heinz, Mar 01 2011

nonn

In general there exist different maximal subsets for a given n. One of these is S = {1, n} union ({primes <= n} \ {prime factors of n}). The number of different subsets is A186994(n).

Max { a(i) : i=1..n } = A036234(n).

			a(4) = 3 because 4 and 2 are not coprime and {1,3,4} is a maximal subset of {1,2,3,4} with pairwise coprime elements.
a(9) = 5, the maximal subsets are {1,2,5,7,9}, {1,4,5,7,9}, {1,5,7,8,9}.

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A001221, A000720, A186994, A036234.

with(numtheory):
a:= n-> `if`(n<4, n, pi(n) -nops(factorset(n)) +2):
seq(a(n), n=1..120);

a(n) = n if n<4, a(n) = A000720(n) - A001221(n) + 2 else.

A131377 a(n) = (pi(n)+1) mod 2.

Original entry on oeis.org

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

Offset: 0

Paolo P. Lava and Giorgio Balzarotti, Jul 04 2007

Old name was: Starting with 1, the sequence a(n) changes from 1 to 0 or back when the next number n is a prime.

Möbius transform of A345220(n). - Wesley Ivan Hurt, Jul 05 2025

			n = 0, 1, 2, 3, 4, 5, etc..
a(n)= 1, 1, 0, 1, 1, 0, etc.
Starting with 1 the sequence changes when we move from 1 to 2 because 2 is prime, again from 2 to 3 because also 3 is prime, then from 4 to 5 being 5 prime and so on.

Cf. A000035 (n mod 2), A000720 (pi), A008683 (mu), A036234, A131378, A345220.

Cf. A071986. - Omar E. Pol, Feb 19 2011

P:=proc(n) local i,k; k:=1; for i from 0 by 1 to n do if isprime(i) then if k=1 then k:=0; else k:=1; fi; fi; print(k); od; end: P(100);

Table[Mod[PrimePi[n] + 1, 2], {n, 0, 100}] (* Wesley Ivan Hurt, Jul 05 2025 *)

a(n) = 1 - A071986(n).
From Wesley Ivan Hurt, Jul 05 2025: (Start)
a(n) = A000035(A036234(n)).
a(n) = Sum_{d|n} A345220(d) * mu(n/d). (End)

New name from Wesley Ivan Hurt, Jul 05 2025

A245820 Permutation of natural numbers induced when A245704 is restricted to {1} and binary codes for polynomials reducible over GF(2): a(1) = 1, a(n) = A062298(A245704(A091242(n-1))).

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 9, 6, 10, 13, 16, 8, 11, 14, 17, 22, 26, 15, 19, 20, 23, 27, 34, 39, 25, 12, 29, 31, 35, 40, 50, 24, 56, 37, 21, 43, 46, 38, 51, 57, 70, 48, 36, 78, 53, 33, 61, 18, 65, 55, 71, 79, 95, 67, 52, 30, 106, 75, 49, 42, 85, 54, 28, 89, 77, 96, 107, 74, 126, 92, 73, 45, 141, 98, 101, 69, 59, 116, 76, 41, 120, 105

Offset: 1

Antti Karttunen, Aug 16 2014

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10001
Index entries for sequences that are permutations of the natural numbers

Inverse: A245819.
Related permutations: A245704, A245813, A245816.
Cf. A014580, A036234, A062298, A091242.

\\ The rest of code can be found in A245704.
A245820(n) = if(1==n, 1, 1 + A245704(n-1));

(define (A245820 n) (if (<= n 1) n (+ 1 (A245704 (- n 1)))))

(define (A245820 n) (if (<= n 1) n (A062298 (A245704 (A091242 (- n 1))))))

(define (A245820 n) (if (<= n 1) n (A036234 (A245704 (A014580 (- n 1))))))

a(1) = 1, and for n > 1, a(n) = 1 + A245704(n-1).
a(1) = 1, and for n > 1, a(n) = A062298(A245704(A091242(n-1))). [Induced when A245704 is restricted to {1} and binary codes for polynomials reducible over GF(2)].
a(1) = 1, and for n > 1, a(n) = A036234(A245704(A014580(n-1))). [Induced also when A245703 is restricted to {1} and other binary codes for polynomials not reducible over GF(2)].
As a composition of related permutations:
a(n) = A245816(A245813(n)).

A080786 Triangle T(n,k) = number of k-smooth numbers <= n, read by rows.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 1, 3, 4, 4, 1, 3, 4, 4, 5, 1, 3, 5, 5, 6, 6, 1, 3, 5, 5, 6, 6, 7, 1, 4, 6, 6, 7, 7, 8, 8, 1, 4, 7, 7, 8, 8, 9, 9, 9, 1, 4, 7, 7, 9, 9, 10, 10, 10, 10, 1, 4, 7, 7, 9, 9, 10, 10, 10, 10, 11, 1, 4, 8, 8, 10, 10, 11, 11, 11, 11, 12, 12, 1, 4, 8, 8, 10, 10, 11, 11, 11, 11, 12, 12, 13, 1, 4

Offset: 1

Reinhard Zumkeller, Mar 12 2003

T(n,n-1) = A014684(n) for n>1;
T(n,2) = A029837(n) for n>1; T(n,3) = A071521(n) for n>2; T(n,5) = A071520(n) for n>4.
A036234(n) = number of distinct terms in n-th row. - Reinhard Zumkeller, Sep 17 2013

			Triangle begins:
.................. 1
................ 1...2
.............. 1...2...3
............ 1...3...4...4
.......... 1...3...4...4...5
........ 1...3...5...5...6...6
...... 1...3...5...5...6...6...7
.... 1...4...6...6...7...7...8...8
.. 1...4...7...7...8...8...9...9...9.

Reinhard Zumkeller, Rows n=1..120 of triangle, flattened
Eric Weisstein's World of Mathematics, Smooth Number.

Cf. A000079, A002473, A003586, A006530, A014684, A029837, A036234, A051037, A051038, A071520, A071521, A080197, A080681, A080682, A080683.

a080786 n k = a080786_tabl !! (n-1) !! (k-1)
a080786_row n = a080786_tabl !! (n-1)
a080786_tabl = map reverse $ iterate f [1] where
   f xs@(x:_) = (x + 1) :
                (zipWith (+) xs (map (fromEnum . (lpf <=)) [x, x-1 ..]))
        where lpf = fromInteger $ a006530 $ fromIntegral (x + 1)
-- Reinhard Zumkeller, Sep 17 2013

A080786 := proc(x,y)
    local a,n ;
    a := 0 ;
    for n from 1 to x do
        if A006530(n) <= y then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Aug 31 2013

P[n_] := FactorInteger[n][[-1, 1]]; P[1]=1; T[n_, k_] := (For[j=0; m=1, m <= n, m++, If[P[m] <= k, j++]]; j); Table[T[n, k], {n, 1, 15}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 22 2015 *)

from itertools import count, islice
from sympy import prevprime, integer_log
def A080786_T(n,k):
    if k==1: return 1
    def g(x,m): return x.bit_length() if m==2 else sum(g(x//(m**i),prevprime(m))for i in range(integer_log(x,m)[0]+1))
    return g(n,prevprime(k+1))
def A080786_gen(): # generator of terms
    return (A080786_T(n,k) for n in count(1) for k in range(1,n+1))
A080786_list = list(islice(A080786_gen(),100)) # Chai Wah Wu, Oct 22 2024

A158973 a(n) = count of numbers k <= n such that all proper divisors of k are divisors of n.

Original entry on oeis.org

1, 2, 3, 4, 4, 6, 5, 7, 6, 7, 6, 11, 7, 9, 9, 10, 8, 12, 9, 13, 11, 11, 10, 17, 11, 12, 12, 14, 11, 18, 12, 16, 14, 14, 14, 20, 13, 15, 15, 20, 14, 20, 15, 19, 20, 17, 16, 25, 17, 20, 18, 20, 17, 23, 19, 24, 19, 19, 18, 29, 19, 21, 24, 24, 21, 25, 20, 24, 22, 27, 21, 32, 22, 24, 26

Offset: 1

Jaroslav Krizek, Apr 01 2009

nonn

For primes p, a(p) = A036234(p) = A000720(p) + 1.

			For n = 8 we have the following proper divisors for k <= n: {1}, {1}, {1}, {1, 2}, {1}, {1, 2, 3}, {1}, {1, 2, 4}. Only k = 6 has a proper divisor that is not a divisor of 8, viz. 3. Hence a(8) = 7.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000040, A000720, A036234.

[ #[ k: k in [1..n] | forall(t){ d: d in Divisors(k) | d eq k or d in Divisors(n) } ]: n in [1..75] ];

N:= 1000: # to get a(1) to a(N)
A:= Vector(N, numtheory:-tau):
for p in select(isprime,[2,seq(i,i=3..N,2)]) do
for d from 0 to floor(log[p](N))-1 do
  R:= [seq(seq(p^d*(i+p*j), j=1..floor((N/p^d - i)/p)), i=1..p-1)];
  A[R]:= map(`+`,A[R],1);
od
od:
convert(A,list); # Robert Israel, Nov 24 2015

f[n_] := Block[{d = Most@ Divisors@ n}, Select[Range@ n, Union[Most@ Divisors@ #, d] == d &]]; Array[Length@ f@ # &, {75}] (* Michael De Vlieger, Nov 25 2015 *)

a004788(n) = {sfp = Set(); for (k=1, n-1, sfp = setunion(sfp, Set(factor(binomial(n, k))[, 1]))); return (length(sfp));}
a(n) = numdiv(n) + a004788(n-1); \\ Altug Alkan, Nov 25 2015

a(n) = A000005(n) + A004788(n-1). - Vladeta Jovovic, Apr 07 2009 (Corrected by Altug Alkan, Nov 25 2015)

Edited and extended by Klaus Brockhaus, Apr 06 2009

A158974 a(n) is the number of numbers k <= n such that not all proper divisors of k are divisors of n.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 2, 1, 3, 3, 5, 1, 6, 5, 6, 6, 9, 6, 10, 7, 10, 11, 13, 7, 14, 14, 15, 14, 18, 12, 19, 16, 19, 20, 21, 16, 24, 23, 24, 20, 27, 22, 28, 25, 25, 29, 31, 23, 32, 30, 33, 32, 36, 31, 36, 32, 38, 39, 41, 31, 42, 41, 39, 40, 44, 41, 47, 44, 47, 43, 50, 40, 51, 50, 49, 50

Offset: 1

Jaroslav Krizek, Apr 01 2009

nonn

			For n = 8 we have the following proper divisors for k <= n: {1}, {1}, {1}, {1, 2}, {1}, {1, 2, 3}, {1}, {1, 2, 4}. Only k = 6 has a proper divisor that is not a divisor of 8, viz. 3. Hence a(8) = 1.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000040, A036234, A000720, A158973.

[ #[ k: k in [1..n] | exists(t){ d: d in Divisors(k) | d ne k and d notin Divisors(n) } ]: n in [1..76] ];

f:= proc(n) local d;
   d:= numtheory:-divisors(n);
   nops(remove(t -> (numtheory:-divisors(t) minus {t}) subset d, [$4..n-1]))
end proc:
map(f, [$1..100]); # Robert Israel, Mar 30 2020

a[n_] := Select[Most[Divisors[#]]& /@ Range[n], AnyTrue[#, !Divisible[n, #]&]&] // Length;
Array[a, 100] (* Jean-François Alcover, Jul 17 2020 *)

a(n) = my(dn = divisors(n)); sum(k=1, n, my(dk=setminus(divisors(k), Set(k))); #setintersect(dk, dn) != #dk); \\ Michel Marcus, Aug 27 2020

For primes p, a(p) = p - A036234(p) = p - A000720(p) - 1.

Edited and extended by Klaus Brockhaus, Apr 06 2009

A076359 a(n) = denominator(n!/phi(n!)).

Original entry on oeis.org

1, 1, 1, 1, 4, 4, 8, 8, 8, 8, 16, 16, 192, 192, 192, 192, 3072, 3072, 55296, 55296, 55296, 55296, 110592, 110592, 110592, 110592, 110592, 110592, 442368, 442368, 13271040, 13271040, 13271040, 13271040, 13271040, 13271040, 477757440

Offset: 1

Labos Elemer, Oct 08 2002

Numerator of Product_{p<=n, p prime} (1 - 1/p). - Franz Vrabec, Jan 28 2014

Robert Israel, Table of n, a(n) for n = 1..2926

Cf. A000005, A000142, A036234, A038110, A048855, A076358.

P:= 1: p:= 1:  v:= 1:
while p < 100 do q:= nextprime(p);
   for i from p to q-1 do A[i]:= v od;
   P:= P * (1-1/q);
   v:= numer(P);
   p:= q;
od:
seq(A[i],i=1..q-1); # Robert Israel, Oct 18 2018

dnf[n_]:=With[{nn=n!},Denominator[nn/EulerPhi[nn]]]; Array[dnf,40] (* Harvey P. Dale, Feb 21 2015 *)

a(n) = numerator(prod(p=1, n, if (isprime(p),(1-1/p), 1))); \\ Michel Marcus, Jan 28 2014

a(n) = denominator(A000142(n)/A048855(n)).

a(n) = A038110(A036234(n)). - Robert Israel, Oct 18 2018

cp's OEIS Frontend

A187106 Number of nonempty subsets of {1, 2, ..., n} having pairwise coprime elements.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A356068 Number of integers ranging from 1 to n that are not prime-powers (1 is not a prime-power).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A379311 Number of prime indices of n that are 1 or prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A186971 Maximal cardinality of a subset of {1, 2, ..., n} containing n and having pairwise coprime elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A131377 a(n) = (pi(n)+1) mod 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A245820 Permutation of natural numbers induced when A245704 is restricted to {1} and binary codes for polynomials reducible over GF(2): a(1) = 1, a(n) = A062298(A245704(A091242(n-1))).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Scheme

Scheme

Scheme

Formula

A080786 Triangle T(n,k) = number of k-smooth numbers <= n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

A158973 a(n) = count of numbers k <= n such that all proper divisors of k are divisors of n.

Views