A007978 Least non-divisor of n.

2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 7, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3

Offset: 1

Author

Jeffrey Shallit

Keywords

• nonn

Comments

Least k >= 2 such that sigma(n) divides sigma(n*k), where sigma is A000203. - Benoit Cloitre, Dec 01 2002

Contains all and only the prime powers p^k, k > 0. The first occurrence of p^k is at A003418(p^k-1); so new records occur at indices in A051451. - Franklin T. Adams-Watters, Jun 13 2011

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Bakir Farhi, On the average asymptotic behavior of a certain type of sequences of integers, Integers, Vol. 9 (2009), pp. 555-567.

Crossrefs

Cf. A003418, A051451, A055874, A053669, A061853, A027750, A064859.

Cf. also A266620 (least non-divisor of n!).

Programs

Haskell

import Data.List ((\\))
a007978 = head . ([1..] \\) . a027750_row
-- Reinhard Zumkeller, May 10 2014

Maple

a:= proc(n) local k;
for k from 2 while n mod k = 0 do od:
k
end proc:
seq(a(n),n=1..100); # Robert Israel, Sep 02 2014

Mathematica

Table[k := 1; While[Mod[n, k] == 0, k++]; k, {n, 2000}]  (* Clark Kimberling, Jun 16 2012 *)
Join[{2, 3}, Table[Complement[Range[n], Divisors[n]][[1]], {n, 3, 100}]] (* Alonso del Arte, Sep 23 2017 *)

PARI

a(n) = {my(k=2); while(!(n % k), k++); k;} \\ Michel Marcus, Sep 25 2017

Python

def a(n):
    k = 2
    while not n%k: k += 1
    return k
print([a(n) for n in range(1, 101)]) # Michael S. Branicky, Jul 09 2022

Python

def A007978(n): return next(filter(lambda d:n%d,range(2,n))) if n>2 else n+1 # Chai Wah Wu, Feb 22 2023

Formula

a(n) = A053669(n) + A061853(n) = A055874(n) + 1. - Henry Bottomley, May 10 2001

G.f.: sum(k >= 2, -k*(x^A003418(k) - x^A003418(k-1))/((x^A003418(k) - 1)*(x^A003418(k-1) - 1))). - Robert Israel, Sep 02 2014

From Alonso del Arte, Sep 23 2017: (Start)

a(n) < n for all n > 2.

a(2n + 1) = 2, a(2n) >= 3.

a(2^k) = 3 for k > 0.

a(n!) = prime(pi(n) + 1) for n >= 0, except for a(3!) = 4. (End)

Asymptotic mean: lim_{n->oo} Sum_{k=1..n} a(k) = 1 + A064859 (Farhi, 2009). - Amiram Eldar, Jun 29 2021