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

Author

Nathaniel Shar, Oct 13 2014

Keywords

• nonn

Comments

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

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

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