login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A096216 a(n) = number of terms among {a(1), a(2), a(3), ..., a(n-1)} that are coprime to n; a(1)=1. 13
1, 1, 2, 2, 4, 2, 6, 2, 7, 3, 10, 3, 12, 4, 9, 6, 16, 3, 18, 7, 10, 8, 22, 4, 22, 8, 18, 6, 28, 4, 30, 8, 19, 9, 28, 5, 36, 10, 25, 10, 40, 5, 42, 13, 22, 14, 46, 9, 42, 12, 33, 15, 52, 9, 40, 16, 35, 19, 58, 7, 60, 21, 33, 23, 49, 14, 66, 25, 42, 15, 70, 15, 72, 28, 34, 26, 55, 15, 78 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

A family of related sequences can be generated using different positive integers for a(1).

LINKS

Peter Kagey, Table of n, a(n) for n = 1..10000

FORMULA

If, for a given fixed a(1), b(n,j) = number of a(k)'s which are multiples of j, for 1 <= k <= n-1, then: a(n) = Sum_{j|n} mu(j)*b(n,j), where mu(j) is the Moebius (Möbius) function.

EXAMPLE

a(1)=1, a(2)=1 and a(9)=7 are those terms, prior to a(10), which are coprime with 10. So a(10) = 3.

MAPLE

a[1]:=1: for n from 2 to 100 do B:=[seq(gcd(n, a[j]), j=1..n-1)]; s:=0: for i from 1 to n-1 do if B[i]=1 then s:=s+1 else s:=s: fi: od: a[n]:=s: od: seq(a[n], n=1..85); # Emeric Deutsch, Aug 01 2005

MATHEMATICA

a[1] = 1; a[n_] := a[n] = Count[ GCD[ Table[ a[i], {i, n - 1}], n], 1]; Table[ a[n], {n, 80}] (* Robert G. Wilson v, Jul 30 2004 *)

PROG

(Perl) #!/usr/bin/perl -w

use bigint; # only because it is an easy way to get gcd()

$| = $n = 1;

@a = (0);

while (1) {

$v = grep $n->bgcd($_) == 1, @a;

print $a[ $n++ ] = $v, " ";

} # Hugo van der Sanden, Mar 30 2006

(PARI) lista(nn) = {va = vector(nn); print1(va[1]=1, ", "); for (n=2, nn, va[n] = sum(k=1, n-1, gcd(va[k], n) == 1); print1(va[n], ", "); ); } \\ Michel Marcus, Apr 10 2016

CROSSREFS

Cf. A056149, A116537.

Sequence in context: A127835 A117004 A128982 * A121599 A080221 A137849

Adjacent sequences:  A096213 A096214 A096215 * A096217 A096218 A096219

KEYWORD

nonn

AUTHOR

Leroy Quet, Jul 28 2004

EXTENSIONS

Edited and extended by Robert G. Wilson v, Jul 30 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 20 21:29 EDT 2019. Contains 326155 sequences. (Running on oeis4.)