login
A248737
a(0) = 0; a(n) = smallest k such that gcd(a(n-k), n) is not 1.
2
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
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
KEYWORD
nonn
AUTHOR
Nathaniel Shar, Oct 13 2014
STATUS
approved