A008578 -id:A008578 - cp's OEIS frontend

A033676 Largest divisor of n <= sqrt(n).

1, 1, 1, 2, 1, 2, 1, 2, 3, 2, 1, 3, 1, 2, 3, 4, 1, 3, 1, 4, 3, 2, 1, 4, 5, 2, 3, 4, 1, 5, 1, 4, 3, 2, 5, 6, 1, 2, 3, 5, 1, 6, 1, 4, 5, 2, 1, 6, 7, 5, 3, 4, 1, 6, 5, 7, 3, 2, 1, 6, 1, 2, 7, 8, 5, 6, 1, 4, 3, 7, 1, 8, 1, 2, 5, 4, 7, 6, 1, 8, 9, 2, 1, 7, 5, 2, 3

Offset: 1

N. J. A. Sloane

a(n) = sqrt(n) is a new record if and only if n is a square. - Zak Seidov, Jul 17 2009
a(n) = A060775(n) unless n is a square, when a(n) = A033677(n) = sqrt(n) is strictly larger than A060775(n). It would be nice to have an efficient algorithm to calculate these terms when n has a large number of divisors, as for example in A060776, A060777 and related problems such as A182987. - M. F. Hasler, Sep 20 2011
a(n) = 1 when n = 1 or n is prime. - Alonso del Arte, Nov 25 2012
a(n) is the smallest central divisor of n. Column 1 of A207375. - Omar E. Pol, Feb 26 2019
a(n^4+n^2+1) = n^2-n+1: suppose that n^2-n+k divides n^4+n^2+1 = (n^2-n+k)*(n^2+n-k+2) - (k-1)*(2*n+1-k) for 2 <= k <= 2*n, then (k-1)*(2*n+1-k) >= n^2-n+k, or n^2 - (2*k-1)*n + (k^2-k+1) = (n-k+1/2)^2 + 3/4 < 0, which is impossible. Hence the next smallest divisor of n^4+n^2+1 than n^2-n+1 is at least n^2-n+(2*n+1) = n^2+n+1 > sqrt(n^4+n^2+1). - Jianing Song, Oct 23 2022

G. Tenenbaum, pp. 268 ff, in: R. L. Graham et al., eds., Mathematics of Paul Erdős I.

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

Cf. A033677 (n/a(n)), A000196 (sqrt), A027750 (list of divisors), A056737 (n/a(n) - a(n)), A219695 (half of this for odd numbers), A207375 (list the central divisor(s)).
The strictly inferior case is A060775. Cf. also A140271.
Indices of given values: A008578 (1 and the prime numbers: a(n) = 1), A161344 (a(n) = 2), A161345 (a(n) = 3), A161424 (4), A161835 (5), A162526 (6), A162527 (7), A162528 (8), A162529 (9), A162530 (10), A162531 (11), A162532 (12), A282668 (indices of primes).

a033676 n = last $ takeWhile (<= a000196 n) $ a027750_row n
-- Reinhard Zumkeller, Jun 04 2012

A033676 := proc(n) local a,d; a := 0 ; for d in numtheory[divisors](n) do if d^2 <= n then a := max(a,d) ; end if; end do: a; end proc: # R. J. Mathar, Aug 09 2009

largestDivisorLEQR[n_Integer] := Module[{dvs = Divisors[n]}, dvs[[Ceiling[Length@dvs/2]]]]; largestDivisorLEQR /@ Range[100] (* Borislav Stanimirov, Mar 28 2010 *)
Table[Last[Select[Divisors[n],#<=Sqrt[n]&]],{n,100}] (* Harvey P. Dale, Mar 17 2017 *)

A033676(n) = {local(d);if(n<2,1,d=divisors(n);d[(length(d)+1)\2])} \\ Michael B. Porter, Jan 30 2010

from sympy import divisors
def A033676(n):
    d = divisors(n)
    return d[(len(d)-1)//2]  # Chai Wah Wu, Apr 05 2021

a(n) = n / A033677(n).
a(n) = A161906(n,A038548(n)). - Reinhard Zumkeller, Mar 08 2013
a(n) = A162348(2n-1). - Daniel Forgues, Sep 29 2014

A014963 Exponential of Mangoldt function M(n): a(n) = 1 unless n is a prime or prime power, in which case a(n) = that prime.

Original entry on oeis.org

1, 2, 3, 2, 5, 1, 7, 2, 3, 1, 11, 1, 13, 1, 1, 2, 17, 1, 19, 1, 1, 1, 23, 1, 5, 1, 3, 1, 29, 1, 31, 2, 1, 1, 1, 1, 37, 1, 1, 1, 41, 1, 43, 1, 1, 1, 47, 1, 7, 1, 1, 1, 53, 1, 1, 1, 1, 1, 59, 1, 61, 1, 1, 2, 1, 1, 67, 1, 1, 1, 71, 1, 73, 1, 1, 1, 1, 1, 79, 1, 3, 1, 83, 1, 1, 1, 1, 1, 89, 1, 1, 1, 1, 1, 1

Offset: 1

Marc LeBrun

There are arbitrarily long runs of ones (Sierpiński). - Franz Vrabec, Sep 26 2005
a(n) is the smallest positive integer such that n divides Product_{k=1..n} a(k), for all positive integers n. - Leroy Quet, May 01 2007
For n>1, resultant of the n-th cyclotomic polynomial with the 1st cyclotomic polynomial x-1. - Ralf Stephan, Aug 14 2013
A368749(n) is the smallest prime p such that the interval [a(p), a(q)] contains n 1's; q = nextprime(p), n >= 0. - David James Sycamore, Mar 21 2024

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, Section 17.7.
I. Vardi, Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 146-147, 152-153 and 249, 1991.

T. D. Noe, Table of n, a(n) for n = 1..10000
Peter Luschny and Stefan Wehmeier, The lcm(1,2,...,n) as a product of sine values sampled over the points in Farey sequences, arXiv:0909.1838 [math.CA], 2009.
Greg Martin, A product of Gamma function values at fractions with the same denominator, arXiv:0907.4384 [math.CA], 2009.
Carl McTague, On the Greatest Common Divisor of C(q*n,n), C(q*n,2*n), ...C(q*n,q*n-q), arXiv:1510.06696 [math.CO], 2015.
A. Nowicki, Strong divisibility and LCM-sequences, arXiv:1310.2416 [math.NT], 2013.
A. Nowicki, Strong divisibility and LCM-sequences, Am. Math. Mnthly 122 (2015), 958-966.
W. Sierpiński, On the numbers [1,2,...n], (Polish) Wiadom. Mat. (2) 9 1966 9-10.
Eric Weisstein's World of Mathematics, Mangoldt Function.
Eric Weisstein's World of Mathematics, Sylvester Cyclotomic Number.
Index entries for sequences related to lcm's

Apart from initial 1, same as A020500. With ones replaced by zeros, equal to A120007.
Cf. A003418, A007947, A008683, A008472, A008578, A048671 (= n/a(n)), A072107 (partial sums), A081386, A081387, A099636, A100994, A100995, A140255 (inverse Mobius transform), A140254 (Mobius transform), A297108, A297109, A340675, A000027, A348846, A368749.
First column of A140256. Row sums of triangle A140581.
Cf. also A140579, A140580 (= n*a(n)).

a014963 1 = 1
a014963 n | until ((> 0) . (`mod` spf)) (`div` spf) n == 1 = spf
          | otherwise = 1
          where spf = a020639 n
-- Reinhard Zumkeller, Sep 09 2011

a := n -> if n < 2 then 1 else numtheory[factorset](n); if 1 < nops(%) then 1 else op(%) fi fi; # Peter Luschny, Jun 23 2009
A014963 := n -> n/ilcm(op(numtheory[divisors](n) minus {1,n}));
seq(A014963(i), i=1..69); # Peter Luschny, Mar 23 2011
# The following is Nowicki's LCM-Transform - N. J. A. Sloane, Jan 09 2024
LCMXFM:=proc(a)  local p,q,b,i,k,n:
if whattype(a) <> list then RETURN([]); fi:
n:=nops(a):
b:=[a[1]]: p:=[a[1]];
for i from 2 to n do q:=[op(p),a[i]]; k := lcm(op(q))/lcm(op(p));
b:=[op(b),k]; p:=q;; od:
RETURN(b); end:
# Alternative, to be called by 'seq' as shown, not for a single n.
a := proc(n) option remember; local i; global f; f := ifelse(n=1, 1, f*n);
iquo(f, mul(a(i)^iquo(n, i), i=1..n-1)) end: seq(a(n), n=1..95); # Peter Luschny, Apr 05 2025

a[n_?PrimeQ] := n; a[n_/;Length[FactorInteger[n]] == 1] := FactorInteger[n][[1]][[1]]; a[n_] := 1; Table[a[n], {n, 95}] (* Alonso del Arte, Jan 16 2011 *)
a[n_] := Exp[ MangoldtLambda[n]]; Table[a[n], {n, 95}] (* Jean-François Alcover, Jul 29 2013 *)
Ratios[LCM @@ # & /@ Table[Range[n], {n, 100}]] (* Horst H. Manninger, Mar 08 2024 *)
Table[Which[PrimeQ[n],n,PrimePowerQ[n],Surd[n,FactorInteger[n][[-1,2]]],True,1],{n,100}] (* Harvey P. Dale, Mar 01 2025 *)

A014963(n)=
{
    local(r);
    if( isprime(n), return(n));
    if( ispower(n,,&r) && isprime(r), return(r) );
    return(1);
}  \\ Joerg Arndt, Jan 16 2011

a(n)=ispower(n,,&n);if(isprime(n),n,1) \\ Charles R Greathouse IV, Jun 10 2011

from sympy import factorint
def A014963(n):
    y = factorint(n)
    return list(y.keys())[0] if len(y) == 1 else 1
print([A014963(n) for n in range(1, 71)]) # Chai Wah Wu, Sep 04 2014

def A014963(n) : return simplify(exp(add(moebius(d)*log(n/d) for d in divisors(n))))
[A014963(n) for n in (1..50)]  # Peter Luschny, Feb 02 2012

def a(n):
    if n == 1: return 1
    return prod(1 - E(n)**k for k in ZZ(n).coprime_integers(n+1))
[a(n) for n in range(1, 14)] # F. Chapoton, Mar 17 2020

a(n) = A003418(n) / A003418(n-1) = lcm {1..n} / lcm {1..n-1}. [This is equivalent to saying that this sequence is the LCM-transform (as defined by Nowicki, 2013) of the positive integers. - David James Sycamore, Jan 09 2024.]
a(n) = 1/Product_{d|n} d^mu(d) = Product_{d|n} (n/d)^mu(d). - Vladeta Jovovic, Jan 24 2002
a(n) = gcd( C(n+1,1), C(n+2,2), ..., C(2n,n) ) where C(n,k) = binomial(n,k). - Benoit Cloitre, Jan 31 2003
a(n) = gcd(C(n,1), C(n+1,2), C(n+2,3), ...., C(2n-2,n-1)), where C(n,k) = binomial(n,k). - Benoit Cloitre, Jan 31 2003; corrected by Ant King, Dec 27 2005
Note: a(n) != gcd(A008472(n), A007947(n)) = A099636(n), GCD of rad(n) and sopf(n) (this fails for the first time at n=30), since a(30) = 1 but gcd(rad(30), sopf(30)) = gcd(30,10) = 10.
a(n)^A100995(n) = A100994(n). - N. J. A. Sloane, Feb 20 2005
a(n) = Product_{k=1..n-1, if(gcd(n, k)=1, 1-exp(2*Pi*i*k/n), 1)}, i=sqrt(-1); a(n) = n/A048671(n). - Paul Barry, Apr 15 2005
Sum_{n>=1} (log(a(n))-1)/n = -2*A001620 [Bateman Manuscript Project Vol III, ed. by Erdelyi et al.]. - R. J. Mathar, Mar 09 2008
n*a(n) = A140580(n) = n^2/A048671(n) = A140579 * [1,2,3,...]. - Gary W. Adamson, May 17 2008
a(n) = (2*Pi)^phi(n) / Product_{gcd(n,k)=1} Gamma(k/n)^2 (for n > 1). - Peter Luschny, Aug 08 2009
a(n) = A166140(n) / A166142(n). - Mats Granvik, Oct 08 2009
a(n) = GCD of rows in A167990. - Mats Granvik, Nov 16 2009
a(n) = A010055(n)*(A007947(n) - 1) + 1. - Reinhard Zumkeller, Mar 26 2010
a(n) = 1 + (A007947(n)-1) * floor(1/A001221(n)), for n>1. - Enrique Pérez Herrero, Jun 01 2011
a(n) = Product_{k=1..n-1} if(gcd(k,n)=1, 2*sin(Pi*k/n), 1). - Peter Luschny, Jun 09 2011
a(n) = exp(Sum_{k>=1} A191898(n,k)/k) for n>1 (conjecture). - Mats Granvik, Jun 19 2011
Dirichlet g.f.: Sum_{n>0} e^Lambda(n)/n^s = Zeta(s) + Sum_{p prime} Sum_{k>0} (p-1)/p^(k*s) = Zeta(s) - ppzeta(s) + Sum(p prime, p/(p^s-1)); for a ppzeta definition see A010055. - Enrique Pérez Herrero, Jan 19 2013
a(n) = exp(lim_{s->1} zeta(s)*Sum_{d|n} moebius(d)/d^(s-1)) for n>1. - Mats Granvik, Jul 31 2013
a(n) = gcd_{k=1..n-1} binomial(n,k) for n > 1, see A014410. - Michel Marcus, Dec 08 2015 [Corrected by Jinyuan Wang, Mar 20 2020]
a(n) = 1 + Sum_{k=2..n} (k-1)*A010051(k)*(floor(k^n/n) - floor((k^n - 1)/n)). - Anthony Browne, Jun 16 2016
The Dirichlet series for log(a(n)) = Lambda(n) is given by the logarithmic derivative of the zeta function -zeta'(s)/zeta(s). - Mats Granvik, Oct 30 2016
a(n) = A008578(1+A297109(n)), For all n >= 1, Product_{d|n} a(d) = n. - Antti Karttunen, Feb 01 2021
Product_{k=1..floor(n/2)} Product_{j=1..floor(n/k)} a(j) = n!. - Ammar Khatab, Jan 28 2025

Additional reference from Eric W. Weisstein, Jun 29 2008

A246547 Prime powers p^e where p is a prime and e >= 2 (prime powers without the primes or 1).

Original entry on oeis.org

4, 8, 9, 16, 25, 27, 32, 49, 64, 81, 121, 125, 128, 169, 243, 256, 289, 343, 361, 512, 529, 625, 729, 841, 961, 1024, 1331, 1369, 1681, 1849, 2048, 2187, 2197, 2209, 2401, 2809, 3125, 3481, 3721, 4096, 4489, 4913, 5041, 5329, 6241, 6561, 6859, 6889, 7921, 8192, 9409, 10201, 10609, 11449, 11881, 12167, 12769, 14641

Offset: 1

Joerg Arndt, Aug 29 2014

These are sometimes called the proper prime powers.
A proper subset of A001597.
Equals A000961 \ A008578 = { x in A001597 | A001221(x)=1 }. - M. F. Hasler, Aug 29 2014

Jens Kruse Andersen, Table of n, a(n) for n = 1..10000
Chai Wah Wu, Algorithms for complementary sequences, arXiv:2409.05844 [math.NT], 2024.

Essentially the same as A025475.
Cf. A000961, A001597, A025528, A051953, A136141, A246655.
There are four different sequences which may legitimately be called "prime powers": A000961 (p^k, k >= 0), A246655 (p^k, k >= 1), A246547 (p^k, k >= 2), A025475 (p^k, k=0 and k >= 2). When you refer to "prime powers", be sure to specify which of these you mean. Also A001597 is the sequence of nontrivial powers n^k, n >= 1, k >= 2. - N. J. A. Sloane, Mar 24 2018

isA246547 := proc(n)
    local ifs;
    ifs := ifactors(n)[2] ;
    if nops(ifs) <> 1 then
        false;
    else
        is(op(2, op(1, ifs)) > 1);
    end if;
end proc:
for n from 2 do
    if isA246547(n) then
        print(n) ;
    end if;
end do: # R. J. Mathar, Feb 01 2016 # Or:
isA246547 := n -> not isprime(n) and nops(numtheory:-factorset(n)) = 1:
select(isA246547, [$1..10000]); # Peter Luschny, May 01 2018

With[{upto=15000},Complement[Select[Range[upto],PrimePowerQ],Prime[ Range[ PrimePi[ upto]]]]] (* Harvey P. Dale, Nov 28 2014 *)
Select[ Range@ 15000, PrimePowerQ@# && !SquareFreeQ@# &] (* Robert G. Wilson v, Dec 01 2014 *)
With[{n = 15000}, Union@ Flatten@ Table[Array[p^# &, Floor@ Log[p, n] - 1, 2], {p, Prime@ Range@ PrimePi@ Sqrt@ n}] ] (* Michael De Vlieger, Jul 06 2018, faster program *)

for(n=1,10^5,if(isprimepower(n)>=2,print1(n,", ")));

m=10^5; v=[]; forprime(p=2, sqrtint(m), e=2; while(p^e<=m, v=concat(v, p^e); e++)); v=vecsort(v) \\ Faster program. Jens Kruse Andersen, Aug 29 2014

from sympy import primepi, integer_nthroot
def A246547(n):
    def f(x): return int(n-1+x-sum(primepi(integer_nthroot(x,k)[0]) for k in range(2,x.bit_length())))
    kmin, kmax = 1,2
    while f(kmax) >= kmax:
        kmax <<= 1
    while True:
        kmid = kmax+kmin>>1
        if f(kmid) < kmid:
            kmax = kmid
        else:
            kmin = kmid
        if kmax-kmin <= 1:
            break
    return kmax # Chai Wah Wu, Aug 14 2024

def A246547List(n):
    return [p for p in srange(2, n) if p.is_prime_power() and not p.is_prime()]
print(A246547List(14642))  # Peter Luschny, Sep 16 2023

a(n) = A025475(n+1). - M. F. Hasler, Aug 29 2014

Sum_{n>=1} 1/a(n) = Sum_{p prime} 1/(p*(p-1)) = A136141. - Amiram Eldar, Dec 21 2020

A048050 Chowla's function: sum of divisors of n except for 1 and n.

Original entry on oeis.org

0, 0, 0, 2, 0, 5, 0, 6, 3, 7, 0, 15, 0, 9, 8, 14, 0, 20, 0, 21, 10, 13, 0, 35, 5, 15, 12, 27, 0, 41, 0, 30, 14, 19, 12, 54, 0, 21, 16, 49, 0, 53, 0, 39, 32, 25, 0, 75, 7, 42, 20, 45, 0, 65, 16, 63, 22, 31, 0, 107, 0, 33, 40, 62, 18, 77, 0, 57, 26, 73, 0, 122, 0, 39, 48, 63, 18, 89

Offset: 1

N. J. A. Sloane

a(n) = 0 if and only if n is a noncomposite number (cf. A008578). - Omar E. Pol, Jul 31 2012
If n is semiprime, a(n) = A008472(n). - Wesley Ivan Hurt, Aug 22 2013
If n = p*q where p and q are distinct primes then a(n) = p+q.
If k,m > 1 are coprime, then a(k*m) = a(k)*a(m) + (m+1)*a(k) + (k+1)*a(m) + k + m. - Robert Israel, Apr 28 2015
a(n) is also the total number of parts in the partitions of n into equal parts that contain neither 1 nor n as a part (see example). More generally, a(n) is the total number of parts congruent to 0 mod k in the partitions of k*n into equal parts that contain neither k nor k*n as a part. - Omar E. Pol, Nov 24 2019
Named after the Indian-American mathematician Sarvadaman D. S. Chowla (1907-1995). - Amiram Eldar, Mar 09 2024

			For n = 20 the divisors of 20 are 1,2,4,5,10,20, so a(20) = 2+4+5+10 = 21.
On the other hand, the partitions of 20 into equal parts that contain neither 1 nor 20 as a part are [10,10], [5,5,5,5], [4,4,4,4,4], [2,2,2,2,2,2,2,2,2,2]. There are 21 parts, so a(20) = 21. - _Omar E. Pol_, Nov 24 2019

James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 92.

T. D. Noe, Table of n, a(n) for n = 1..10000
M. Lal and A. Forbes, A note on Chowla's function, Math. Comp., 25 (1971), 923-925.
Abdur Rahman Nasir, On a certain arithmetic function, Bull. Calcutta Math. Soc., Vol. 38 (1946), p. 140.
Omar E. Pol, Illustration of initial terms obtained geometrically.

Cf. A000203, A001065, A000593, A002954, A048995, A007956, A048671, A182936.

Cf. A057533, A005276, A027751, A237593, A245092, A244049 (partial sums).

a048050 1 = 0
a048050 n = (subtract 1) $ sum $ a027751_row n
-- Reinhard Zumkeller, Feb 09 2013

A048050:=func< n | n eq 1 or IsPrime(n) select 0 else &+[ a: a in Divisors(n) | a ne 1 and a ne n ] >; [ A048050(n): n in [1..100] ]; // Klaus Brockhaus, Mar 04 2011

A048050 := proc(n) if n > 1 then numtheory[sigma](n)-1-n ; else 0; end if; end proc:

f[n_]:=Plus@@Divisors[n]-n-1; Table[f[n],{n,100}] (*Vladimir Joseph Stephan Orlovsky, Sep 13 2009*)
Join[{0},DivisorSigma[1,#]-#-1&/@Range[2,80]] (* Harvey P. Dale, Feb 25 2015 *)

a(n)=if(n>1,sigma(n)-n-1,0) \\ Charles R Greathouse IV, Nov 20 2012

from sympy import divisors
def a(n): return sum(divisors(n)[1:-1]) # Indranil Ghosh, Apr 26 2017

from sympy import divisor_sigma
def A048050(n): return 0 if n == 1 else divisor_sigma(n)-n-1 # Chai Wah Wu, Apr 18 2021

a(n) = A000203(n) - A065475(n).
a(n) = A001065(n) - 1, n > 1.
For n > 1: a(n) = Sum_{k=2..A000005(n)-1} A027750(n,k). - Reinhard Zumkeller, Feb 09 2013
a(n) = A000203(n) - n - 1, n > 1. - Wesley Ivan Hurt, Aug 22 2013
G.f.: Sum_{k>=2} k*x^(2*k)/(1 - x^k). - Ilya Gutkovskiy, Jan 22 2017

A003309 Ludic numbers: apply the same sieve as Eratosthenes, but cross off every k-th remaining number.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 17, 23, 25, 29, 37, 41, 43, 47, 53, 61, 67, 71, 77, 83, 89, 91, 97, 107, 115, 119, 121, 127, 131, 143, 149, 157, 161, 173, 175, 179, 181, 193, 209, 211, 221, 223, 227, 233, 235, 239, 247, 257, 265, 277, 283, 287, 301, 307, 313

Offset: 1

N. J. A. Sloane

The definition can obviously only be applied from k = a(2) = 2 on: for k = 1, all remaining numbers would be deleted. - M. F. Hasler, Nov 02 2024

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Donovan Johnson, Table of n, a(n) for n = 1..100000
David Applegate, C program for A003309.
Donovan Johnson, Ludic numbers computed up to A003309(1236290) = 23000711.
OEIS Wiki, Ludic numbers.
Popular Computing (Calabasas, CA), Sieves: Problem 43, Vol. 2 (No. 13, Apr 1974), pp. 6-7. This is Sieve #1. [Annotated and scanned copy]
Rosettacode Wiki, Ludic numbers.
Index entries for sequences generated by sieves

Without the initial 1 occurs as the leftmost column in arrays A255127 and A260717.
Cf. A003310, A003311, A100464, A100585, A100586 (variants).
Cf. A192503 (primes in sequence), A192504 (nonprimes), A192512 (number of terms <= n).
Cf. A192490 (characteristic function).
Cf. A192607 (complement).
Cf. A260723 (first differences).
Cf. A255420 (iterates of f(n) = A003309(n+1) starting from n=1).
Subsequence of A302036.
Cf. A237056, A237126, A237427, A235491, A255407, A255408, A255421, A255422, A260435, A260436, A260741, A260742 (permutations constructed from Ludic numbers).
Cf. also A000959, A008578, A255324, A254100, A272565 (Ludic factor of n), A297158, A302032, A302038.
Cf. A376237 (ludic factorial: cumulative product), A376236 (ludic Fortunate numbers).

a003309 n = a003309_list !! (n - 1)
a003309_list = 1 : f [2..] :: [Int]
   where f (x:xs) = x : f (map snd [(u, v) | (u, v) <- zip [1..] xs,
                                             mod u x > 0])
-- Reinhard Zumkeller, Feb 10 2014, Jul 03 2011

ludic:= proc(N) local i, k,S,R;
  S:= {$2..N};
  R:= 1;
  while nops(S) > 0 do
    k:= S[1];
    R:= R,k;
    S:= subsop(seq(1+k*j=NULL, j=0..floor((nops(S)-1)/k)),S);
  od:
[R];
end proc:
ludic(1000); # Robert Israel, Feb 23 2015

t = Range[2, 400]; r = {1}; While[Length[t] > 0, k = First[t]; AppendTo[r, k]; t = Drop[t, {1, -1, k}];]; r (* Ray Chandler, Dec 02 2004 *)

t=vector(399,x,x+1); r=[1]; while(length(t)>0, k=t[1];r=concat(r,[k]);t=vector((length(t)*(k-1))\k,x,t[(x*k+k-2)\(k-1)])); r \\ Phil Carmody, Feb 07 2007

A3309=[1]; next_A003309(n)=nn && break); n+!if(n=setsearch(A3309,n+1,1),return(A3309[n])) \\ Should be made more efficient if n >> max(A3309). - M. F. Hasler, Nov 02 2024
{A003309(n) = while(n>#A3309, next_A003309(A3309[#A3309])); A3309[n]} \\ Should be made more efficient in case n >> #A3309. - M. F. Hasler, Nov 03 2024

upto(nn)= my(r=List([1..nn]), p=1); while(p++<#r, my(k=r[p], i=p); while((i+=k)<=#r, listpop(~r, i); i--)); Vec(r); \\ Ruud H.G. van Tol, Dec 13 2024

remainders = [0]
ludics = [2]
N_MAX = 313
for i in range(3, N_MAX) :
    ludic_index = 0
    while ludic_index < len(ludics) :
        ludic = ludics[ludic_index]
        remainder = remainders[ludic_index]
        remainders[ludic_index] = (remainder + 1) % ludic
        if remainders[ludic_index] == 0 :
            break
        ludic_index += 1
    if ludic_index == len(ludics) :
        remainders.append(0)
        ludics.append(i)
ludics = [1] + ludics
print(ludics)
# Alexandre Herrera, Aug 10 2023

def A003309(): # generator of the infinite list of ludic numbers
    L = [2, 3]; yield 1; yield 2; yield 3
    while k := len(L)//2: # could take min{k | k >= L[-1-k]-1}
        for j in L[-1-k::-1]: k += 1 + k//(j-1)
        L.append(k+2); yield k+2
A003309_upto = lambda N=99: [t for t,_ in zip(A003309(),range(N))]
# M. F. Hasler, Nov 02 2024

(define (A003309 n) (if (= 1 n) n (A255127bi (- n 1) 1))) ;; Code for A255127bi given in A255127.
;; Antti Karttunen, Feb 23 2015

Complement of A192607; A192490(a(n)) = 1. - Reinhard Zumkeller, Jul 05 2011
From Antti Karttunen, Feb 23 2015: (Start)
a(n) = A255407(A008578(n)).
a(n) = A008578(n) + A255324(n).
(End)

More terms from David Applegate and N. J. A. Sloane, Nov 23 2004

A289780 p-INVERT of the positive integers (A000027), where p(S) = 1 - S - S^2.

Original entry on oeis.org

1, 4, 14, 47, 156, 517, 1714, 5684, 18851, 62520, 207349, 687676, 2280686, 7563923, 25085844, 83197513, 275925586, 915110636, 3034975799, 10065534960, 33382471801, 110713382644, 367182309614, 1217764693607, 4038731742156, 13394504020957, 44423039068114

Offset: 0

Clark Kimberling, Aug 10 2017

Suppose s = (c(0), c(1), c(2), ...) is a sequence and p(S) is a polynomial. Let S(x) = c(0)*x + c(1)*x^2 + c(2)*x^3 + ... and T(x) = (-p(0) + 1/p(S(x)))/x. The p-INVERT of s is the sequence t(s) of coefficients in the Maclaurin series for T(x).
Taking p(S) = 1 - S gives the INVERT transform of s, so that p-INVERT is a generalization of the INVERT transform (e.g., A033453).
Guide to p-INVERT sequences using p(S) = 1 - S - S^2:
t(A000012) = t(1,1,1,1,1,1,1,...)    = A001906
t(A000290) = t(1,4,9,16,25,36,...)   = A289779
t(A000027) = t(1,2,3,4,5,6,7,8,...)  = A289780
t(A000045) = t(1,2,3,5,8,13,21,...)  = A289781
t(A000032) = t(2,1,3,4,7,11,14,...)  = A289782
t(A000244) = t(1,3,9,27,81,243,...)  = A289783
t(A000302) = t(1,4,16,64,256,...)    = A289784
t(A000351) = t(1,5,25,125,625,...)   = A289785
t(A005408) = t(1,3,5,7,9,11,13,...)  = A289786
t(A005843) = t(2,4,6,8,10,12,14,...) = A289787
t(A016777) = t(1,4,7,10,13,16,...)   = A289789
t(A016789) = t(2,5,8,11,14,17,...)   = A289790
t(A008585) = t(3,6,9,12,15,18,...)   = A289795
t(A000217) = t(1,3,6,10,15,21,...)   = A289797
t(A000225) = t(1,3,7,15,31,63,...)   = A289798
t(A000578) = t(1,8,27,64,625,...)    = A289799
t(A000984) = t(1,2,6,20,70,252,...)  = A289800
t(A000292) = t(1,4,10,20,35,56,...)  = A289801
t(A002620) = t(1,2,4,6,9,12,16,...)  = A289802
t(A001906) = t(1,3,8,21,55,144,...)  = A289803
t(A001519) = t(1,1,2,5,13,34,...)    = A289804
t(A103889) = t(2,1,4,3,6,5,8,7,,...) = A289805
t(A008619) = t(1,1,2,2,3,3,4,4,...)  = A289806
t(A080513) = t(1,2,2,3,3,4,4,5,...)  = A289807
t(A133622) = t(1,2,1,3,1,4,1,5,...)  = A289809
t(A000108) = t(1,1,2,5,14,42,...)    = A081696
t(A081696) = t(1,1,3,9,29,97,...)    = A289810
t(A027656) = t(1,0,2,0,3,0,4,0,5...) = A289843
t(A175676) = t(1,0,0,2,0,0,3,0,...)  = A289844
t(A079977) = t(1,0,1,0,2,0,3,...)    = A289845
t(A059841) = t(1,0,1,0,1,0,1,...)    = A289846
t(A000040) = t(2,3,5,7,11,13,...)    = A289847
t(A008578) = t(1,2,3,5,7,11,13,...)  = A289828
t(A000142) = t(1!, 2!, 3!, 4!, ...)  = A289924
t(A000201) = t(1,3,4,6,8,9,11,...)   = A289925
t(A001950) = t(2,5,7,10,13,15,...)   = A289926
t(A014217) = t(1,2,4,6,11,17,29,...) = A289927
t(A000045*) = t(0,1,1,2,3,5,...)     = A289975 (* indicates prepended 0's)
t(A000045*) = t(0,0,1,1,2,3,5,...)   = A289976
t(A000045*) = t(0,0,0,1,1,2,3,5,...) = A289977
t(A290990*) = t(0,1,2,3,4,5,...)     = A290990
t(A290990*) = t(0,0,1,2,3,4,5,...)   = A290991
t(A290990*) = t(0,0,01,2,3,4,5,...)  = A290992

			Example 1:  s = (1,2,3,4,5,6,...) = A000027 and p(S) = 1 - S.
S(x) = x + 2x^2 + 3x^3 + 4x^4 + ...
p(S(x)) = 1 - (x + 2x^2 + 3x^3 + 4x^4 + ... )
- p(0) + 1/p(S(x)) = -1 + 1 + x + 3x^2 + 8x^3 + 21x^4 + ...
T(x) = 1 + 3x + 8x^2 + 21x^3 + ...
t(s) = (1,3,8,21,...) = A001906.
***
Example 2:  s = (1,2,3,4,5,6,...) = A000027 and p(S) = 1 - S - S^2.
S(x) =  x + 2x^2 + 3x^3 + 4x^4 + ...
p(S(x)) = 1 - ( x + 2x^2 + 3x^3 + 4x^4 + ...) - ( x + 2x^2 + 3x^3 + 4x^4 + ...)^2
- p(0) + 1/p(S(x)) = -1 + 1 + x + 4x^2 + 14x^3 + 47x^4 + ...
T(x) = 1 + 4x + 14x^2 + 47x^3 + ...
t(s) = (1,4,14,47,...) = A289780.

Clark Kimberling, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5, -7, 5, -1)

Cf. A000027.

P:=[1,4,14,47];; for n in [5..10^2] do P[n]:=5*P[n-1]-7*P[n-2]+5*P[n-3]-P[n-4]; od; P; # Muniru A Asiru, Sep 03 2017

z = 60; s = x/(1 - x)^2; p = 1 - s - s^2;
Drop[CoefficientList[Series[s, {x, 0, z}], x], 1] (* A000027 *)
Drop[CoefficientList[Series[1/p, {x, 0, z}], x], 1] (* A289780 *)

x='x+O('x^99); Vec((1-x+x^2)/(1-5*x+7*x^2-5*x^3+x^4)) \\ Altug Alkan, Aug 13 2017

G.f.: (1 - x + x^2)/(1 - 5 x + 7 x^2 - 5 x^3 + x^4).

a(n) = 5*a(n-1) - 7*a(n-2) + 5*a(n-3) - a(n-4).

A014689 a(n) = prime(n)-n, the number of nonprimes less than prime(n).

Original entry on oeis.org

1, 1, 2, 3, 6, 7, 10, 11, 14, 19, 20, 25, 28, 29, 32, 37, 42, 43, 48, 51, 52, 57, 60, 65, 72, 75, 76, 79, 80, 83, 96, 99, 104, 105, 114, 115, 120, 125, 128, 133, 138, 139, 148, 149, 152, 153, 164, 175, 178, 179, 182, 187, 188, 197, 202, 207, 212, 213, 218, 221, 222

Offset: 1

Mohammad K. Azarian

a(n) = A048864(A000040(n)) = number of nonprimes in RRS of n-th prime. - Labos Elemer, Oct 10 2002
A000040 - A014689 = A000027; in other words, the sequence of natural numbers subtracted from the prime sequence produces A014689. - Enoch Haga, May 25 2009
a(n) = A000040(n) - n. a(n) = inverse (frequency distribution) sequence of A073425(n), i.e., number of terms of sequence A073425(n) less than n. a(n) = A065890(n) + 1, for n >= 1. a(n) - 1 = A065890(n) = the number of composite numbers, i.e., (A002808) less than n-th primes, (i.e., < A000040(n)). - Jaroslav Krizek, Jun 27 2009
a(n) = A162177(n+1) + 1, for n >= 1. a(n) - 1 = A162177(n+1) = the number of composite numbers, i.e., (A002808) less than (n+1)-th number of set {1, primes}, (i.e., < A008578(n+1)). - Jaroslav Krizek, Jun 28 2009
Conjecture: Each residue class contains infinitely many terms of this sequence. Similarly, for any integers m > 0 and r, we have prime(n) + n == r (mod m) for infinitely many positive integers n. - Zhi-Wei Sun, Nov 25 2013
First differences are A046933 = differences minus one between successive primes. - Gus Wiseman, Jan 18 2020

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

Equals A014692 - 1.
Cf. A000040, A033286, A158611, A002808, A065890.
Cf. A232463, A232443.
The sum of prime factors of n is A001414(n).
The sum of prime indices of n is A056239(n).
Their difference is A331415(n).
Cf. A000720, A046933, A056239, A318995, A325036, A331380, A331416, A331418.

a014689 n = a000040 n - fromIntegral n
-- Reinhard Zumkeller, Apr 09 2012

[NthPrime(n)-n: n in [1..70]]; // Vincenzo Librandi, Mar 20 2013

Table[Prime[n] - n, {n, 61}] (* Alonso del Arte *)

a(n) = prime(n)-n \\ Charles R Greathouse IV, Sep 05 2011

from sympy import prime
def A014689(n): return prime(n)-n # Chai Wah Wu, Oct 11 2024

G.f: b(x) - x/((1-x)^2), where b(x) is the g.f. of A000040. - Mario C. Enriquez, Dec 13 2016

More terms from Vasiliy Danilov (danilovv(AT)usa.net), Jul 1998

Correction for Aug 2009 change of offset in A158611 and A008578 by Jaroslav Krizek, Jan 27 2010

A093641 Numbers of form 2^i * prime(j), i>=0, j>0, together with 1.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 16, 17, 19, 20, 22, 23, 24, 26, 28, 29, 31, 32, 34, 37, 38, 40, 41, 43, 44, 46, 47, 48, 52, 53, 56, 58, 59, 61, 62, 64, 67, 68, 71, 73, 74, 76, 79, 80, 82, 83, 86, 88, 89, 92, 94, 96, 97, 101, 103, 104, 106, 107, 109, 112

Offset: 1

Reinhard Zumkeller, Apr 07 2004

a(n) is either 1, prime, or of form 2a(m), m

1 and Heinz numbers of hook integer partitions. The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k). A hook is a partition of the form (n,1,1,...,1). - Gus Wiseman, Sep 15 2018

Numbers whose odd part is noncomposite. - Peter Munn, Aug 06 2020

			55 is not a member, as 5*11 is not of the form 2^i * prime.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

A093640(a(n)) = A000005(a(n)); A000040 and A000079 are subsequences.
A105440 is a subsequence, see also A105442. - Reinhard Zumkeller, Apr 09 2005
Cf. A078822, A007088.
Complement of A105441; A001221(a(n))<=2; A005087(a(n))<=1; A087436(a(n))<=1.
See also A105442.
Union of A038550 and A000079, see also A008578.
Cf. A082733, A153452, A296188, A296561, A300121, A304438, A305940, A317554.
Cf. A000265 (odd part), A008578 (noncomposite).

a093641 n = a093641_list !! (n-1)
a093641_list = filter ((<= 2) . a001227) [1..]
-- Reinhard Zumkeller, May 01 2012

hookQ[n_]:=MatchQ[DeleteCases[FactorInteger[n],{2,}],{}|{{,1}}];
Select[Range[100],hookQ] (* Gus Wiseman, Sep 15 2018 *)

upTo(lim)=my(v=List([1])); for(e=0, log(lim)\log(2), forprime(p=2, lim>>e, listput(v,p<Charles R Greathouse IV, Aug 21 2011

isok(m) = my(k=m/2^valuation(m,2)); (k == 1) || isprime(k); \\ Michel Marcus, Mar 16 2023

from sympy import primepi
def A093641(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n-1+x-sum(primepi(x>>i) for i in range(x.bit_length()))
    return bisection(f,n,n) # Chai Wah Wu, Feb 02 2025

A001227(a(n)) <= 2. - Reinhard Zumkeller, May 01 2012

Number A(x) of a(n) not exceeding x equals 1 + pi(x) + pi(x/2) + pi(x/4) + ..., where pi(x) is the number of primes <= x. If x goes to infinity, A(x)~2*x/log(x) and a(n)~n*log(n)/2 (n-->infinity). - Vladimir Shevelev, Feb 06 2014

A037143 Numbers with at most 2 prime factors (counted with multiplicity).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 46, 47, 49, 51, 53, 55, 57, 58, 59, 61, 62, 65, 67, 69, 71, 73, 74, 77, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 103, 106, 107, 109, 111, 113, 115, 118

Offset: 1

N. J. A. Sloane

nonn

A001222(a(n)) <= 2; A054576(a(n)) = 1. - Reinhard Zumkeller, Mar 10 2006
Products of two noncomposite numbers. - Juri-Stepan Gerasimov, Apr 15 2010
Also, numbers with permutations of all divisors only with coprime adjacent elements: A109810(a(n)) > 0. - Reinhard Zumkeller, May 24 2010
A060278(a(n)) = 0. - Reinhard Zumkeller, Apr 05 2013
1 together with numbers k such that sigma(k) + phi(k) - d(k) = 2k - 2. - Wesley Ivan Hurt, May 03 2015
Products of two not necessarily distinct terms of A008578 (the same relation between A000040 and A001358). - Flávio V. Fernandes, May 28 2021

Felix Fröhlich, Table of n, a(n) for n = 1..10000 (first 1000 terms from Reinhard Zumkeller)
Andreas Weingartner, Uniform distribution of alpha*n modulo one for a family of integer sequences, arXiv:2303.16819 [math.NT], 2023.

Union of A008578 and A001358. Complement of A033942.
Cf. A063928, A001222, A054576, A109810, A060278.
A101040(a(n))=1 for n>1.
Subsequence of A037144. - Reinhard Zumkeller, May 24 2010
A098962 and A139690 are subsequences.

a037143 n = a037143_list !! (n-1)
a037143_list = 1 : merge a000040_list a001358_list where
   merge xs'@(x:xs) ys'@(y:ys) =
         if x < y then x : merge xs ys' else y : merge xs' ys
-- Reinhard Zumkeller, Dec 18 2012

with(numtheory): A037143:=n->`if`(bigomega(n)<3,n,NULL): seq(A037143(n), n=1..200); # Wesley Ivan Hurt, May 03 2015

Select[Range[120], PrimeOmega[#] <= 2 &] (* Ivan Neretin, Aug 16 2015 *)

is(n)=bigomega(n)<3 \\ Charles R Greathouse IV, Apr 29 2015

from math import isqrt
from sympy import primepi, primerange
def A037143(n):
    def f(x): return int(n-2+x-primepi(x)-sum(primepi(x//k)-a for a,k in enumerate(primerange(isqrt(x)+1))))
    kmin, kmax = 1,2
    while f(kmax) >= kmax:
        kmax <<= 1
    while True:
        kmid = kmax+kmin>>1
        if f(kmid) < kmid:
            kmax = kmid
        else:
            kmin = kmid
        if kmax-kmin <= 1:
            break
    return kmax # Chai Wah Wu, Aug 23 2024

More terms from Henry Bottomley, Aug 15 2001

A014688 a(n) = n-th prime + n.

Original entry on oeis.org

3, 5, 8, 11, 16, 19, 24, 27, 32, 39, 42, 49, 54, 57, 62, 69, 76, 79, 86, 91, 94, 101, 106, 113, 122, 127, 130, 135, 138, 143, 158, 163, 170, 173, 184, 187, 194, 201, 206, 213, 220, 223, 234, 237, 242, 245, 258, 271, 276, 279, 284, 291, 294, 305, 312, 319, 326

Offset: 1

Mohammad K. Azarian

Conjecture: this sequence contains an infinite number of primes (A061068), yet contains arbitrarily long "prime deserts" such as the 11 composites in A014688 between a(6) = 19 and a(18) = 79 and the 17 composites in A014688 between a(48) = 271 and a(66) = 383. - Jonathan Vos Post, Nov 22 2004
Does an n exist such that n*prime(n)/(n+prime(n)) is an integer? - Ctibor O. Zizka, Mar 04 2008. The answer to Zizka's question is easily seen to be No: such an integer k would be positive and less than prime(n), but then k*(n + prime(n)) = prime(n)*n would be impossible. - Robert Israel, Apr 20 2015
Complement of A064427. - Jaroslav Krizek, Oct 28 2009
According to a theorem of Lu and Deng (see LINKS), there exists at least one prime number p such that a(n)-n < p <= a(n); equivalently pi(a(n)) - pi(a(n)-n) >= 1 (see A332086). For example, prime number 3 is in the range of (2,3], 5 in (3,5], 7 in (5,8], and 29 & 31 in (23,32]. - Ya-Ping Lu, Sep 02 2020

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Ya-Ping Lu and Shu-Fang Deng, An upper bound for the prime gap, arXiv:2007.15282 [math.GM], 2020.
Carlos Rivera, Puzzle 821. Prime numbers and complementary sequences, The Prime Puzzles and Problems Connection.
Juan Luis Varona, On the Solution of the Equation n = a*k + b*p_k by Means of an Iterative Method, Journal of Integer Sequences, Vol. 24 (2021), Article 21.10.5.

Cf. A000040, A078916, A093570, A093571, A076556, A061068, A332086.

cp's OEIS Frontend

A033676 Largest divisor of n <= sqrt(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A014963 Exponential of Mangoldt function M(n): a(n) = 1 unless n is a prime or prime power, in which case a(n) = that prime.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Sage

Sage

Formula

Extensions

A246547 Prime powers p^e where p is a prime and e >= 2 (prime powers without the primes or 1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

SageMath

Formula

A048050 Chowla's function: sum of divisors of n except for 1 and n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Python

Formula

A003309 Ludic numbers: apply the same sieve as Eratosthenes, but cross off every k-th remaining number.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica