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
Keywords
Examples
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.
Links
- Nathaniel Shar, Table of n, a(n) for n = 0..10000
Crossrefs
Cf. A257173.
Programs
-
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 -
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
Comments