A248737 a(0) = 0; a(n) = smallest k such that gcd(a(n-k), n) is not 1.

0, 1, 2, 3, 2, 5, 2, 7, 2, 6, 1, 11, 3, 13, 5, 1, 7, 17, 6, 19, 2, 3, 2, 23, 2, 11, 2, 6, 1, 29, 3, 31, 5, 3, 7, 1, 3, 37, 11, 3, 8, 41, 2, 43, 2, 6, 1, 47, 3, 15, 1, 2, 1, 53, 3, 6, 1, 2, 1, 59, 3, 61, 5, 3, 7, 3, 1, 67, 11, 4, 1, 71, 3, 73, 5, 1, 7, 1, 6, 79

Offset

0,3

Comments

If p is prime, a(p) = p.

A257173(n) = smallest number m such that a(m) = n. - Reinhard Zumkeller, Apr 17 2015

Links

Nathaniel Shar, Table of n, a(n) for n = 0..10000

Example

a(9) = 6 because a(8) = 2, a(7) = 7, a(6) = 2, a(5) = 5, a(4) = 2 are all relatively prime to 9, but a(3) = 3 is not.

Prog

(PARI) findk(va, n) = {k = 1; while (gcd(va[n-k], n) == 1, k++; if (k==n, break)); k; }
lista(nn) = {va = vector(nn); va[1] = 1; print1(0, ", ", va[1], ", "); for (n=2, nn, va[n] = findk(va, n); print1(va[n], ", "); ); } \\ Michel Marcus, Oct 17 2014
(Haskell)
import Data.List (findIndex); import Data.Maybe (fromMaybe)
a248737 n = a248737_list !! n
a248737_list = 0 : f 1 [0] where
   f x ys = y : f (x + 1) (y : ys) where
     y = (+ 1) $ fromMaybe (x - 1) $ findIndex (\z -> gcd z x /= 1) ys
-- Reinhard Zumkeller, Apr 17 2015

Crossrefs

Cf. A257173.

Sequence in context: A280697 A088444 A108077 * A141310 A007389 A007388

Adjacent sequences: A248734 A248735 A248736 * A248738 A248739 A248740

Keyword

nonn

Author

Nathaniel Shar, Oct 13 2014

Status

approved