A113469 a(0)=1. a(n) = number of positive integers <= n that are not coprime to a(n-1).

1, 0, 2, 1, 0, 5, 1, 0, 8, 4, 5, 2, 6, 8, 7, 2, 8, 8, 9, 6, 13, 1, 0, 23, 1, 0, 26, 14, 16, 14, 17, 1, 0, 33, 13, 2, 18, 24, 25, 7, 5, 8, 21, 18, 29, 1, 0, 47, 1, 0, 50, 30, 38, 27, 18, 36, 37, 1, 0, 59, 1, 0, 62, 32, 32, 32, 33, 26, 37, 1, 0, 71, 1, 0, 74, 38, 40, 46, 41, 1, 0

Offset

0,3

Links

John Tyler Rascoe, Table of n, a(n) for n = 0..10000

Example

a(8) = 8. So a(9) = the number of positive integers <= 9 that are not coprime to 8 (i.e., that are divisible by 2). So a(9) = 4.

Maple

A113469 := proc(n) option remember ; local a, i, aprev ; if n= 0 then RETURN(1) ; fi ; a :=0 ; aprev := A113469(n-1) ; for i from 1 to n do if gcd(i, aprev) <> 1 or aprev=0 then a := a+1 ; fi ; od ; RETURN(a) ; end: for n from 0 to 80 do printf("%d, ", A113469(n)) ; od ; # R. J. Mathar, Jun 07 2007

Mathematica

a[n] = If[n == 0, 1, With[{a1 = a[n-1]}, Length@Select[Range[n], a1 == 0 || !CoprimeQ[#, a1]&]]];
Table[a[n], {n, 0, 80}] (* Jean-François Alcover, Nov 14 2024 *)

Prog

(Python)
from math import gcd
def A113469_list(n_max):
    A = [1]
    for n in range(n_max):
        if A[-1] == 0: A.append(n+1)
        else: A.append(sum(1 for k in range(n+1) if gcd(k+1, A[-1]) != 1))
    return A # John Tyler Rascoe, Nov 14 2024

Crossrefs

Cf. A116204.

Sequence in context: A322119 A363731 A112334 * A060137 A350262 A243821

Adjacent sequences: A113466 A113467 A113468 * A113470 A113471 A113472

Keyword

nonn

Author

Leroy Quet, May 10 2007

Extensions

More terms from R. J. Mathar, Jun 07 2007

Status

approved