A248737 - OEIS

%I #12 Apr 17 2015 16:04:09

%S 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,

%T 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,

%U 61,5,3,7,3,1,67,11,4,1,71,3,73,5,1,7,1,6,79

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

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

%C A257173(n) = smallest number m such that a(m) = n. - _Reinhard Zumkeller_, Apr 17 2015

%H Nathaniel Shar, <a href="/A248737/b248737.txt">Table of n, a(n) for n = 0..10000</a>

%e 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.

%o (PARI) findk(va, n) = {k = 1; while (gcd(va[n-k], n) == 1, k++; if (k==n, break)); k;}

%o 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

%o (Haskell)

%o import Data.List (findIndex); import Data.Maybe (fromMaybe)

%o a248737 n = a248737_list !! n

%o a248737_list = 0 : f 1 [0] where

%o    f x ys = y : f (x + 1) (y : ys) where

%o      y = (+ 1) $ fromMaybe (x - 1) $ findIndex (\z -> gcd z x /= 1) ys

%o -- _Reinhard Zumkeller_, Apr 17 2015

%Y Cf. A257173.

%K nonn

%O 0,3

%A _Nathaniel Shar_, Oct 13 2014