login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A216475 The number of numbers coprime to and less than n+2, excluding 2. 1
1, 2, 3, 2, 5, 4, 5, 4, 9, 4, 11, 6, 7, 8, 15, 6, 17, 8, 11, 10, 21, 8, 19, 12, 17, 12, 27, 8, 29, 16, 19, 16, 23, 12, 35, 18, 23, 16, 39, 12, 41, 20, 23, 22, 45, 16, 41, 20, 31, 24, 51, 18, 39, 24, 35, 28, 57, 16, 59, 30, 35, 32, 47, 20, 65, 32, 43, 24, 69, 24 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

When integer divisions are considered we might pick a fixed nonnegative integer r as divisor for writing every nonnegative integer x as an expression of the form x=yr+z which assigns to x a unique ordered pair (y,z). This would be useful if we were interested in looking for prime numbers by trying to identify some topological or geometrical property instead of meeting arithmetic conditions for algorithms like the Lucas-Lehmer test.

The main interest in such a viewpoint is discarding all the "z" values for a fixed "r" that would not generate a prime number because those modulo "z" and the corresponding fixed divisor "r" are not coprime.

For example, setting r=12 as our divisor would leave only the chance of writing the prime numbers using "z" in {1,5,7,11}. Any other "z" will produce composite numbers.

When r=12, this formula becomes x=12y+z, and for odd numbers (sometimes also prime numbers ) "z" will be always one of the four integers in {1,5,7,11}.

A more interesting result is the following fact: Precisely with r=12 we might code and store a "map" of prime numbers as a computer file composed of ASCII characters (or some similar standard) for further processing in the hope of finding out some pattern or rule for predicting where the next prime will appear.

These ideas are in fact an informal description of a compression algorithm which translates 8-tuples of odd integers into single-byte computer characters, where the meaningful interpretation of such information depends on the offsets for each binary digit inside a byte.

LINKS

R. J. Cano, Table of n, a(n) for n = 1..10005

R. J. Cano, The first 1230 mathching "offset-value" pairs for sequence A216475

R. J. Cano, C program source code for generating this sequence

R. J. Cano, A stub of the b-file explaining briefly how the algorithm works. Please check it together with the C program given here and read the comments.

L. V. Kuz'min, Chinese remainder theorem, Encyclopedia of Mathematics.

FORMULA

a(2n) = phi(2n+2), a(2n+1) = phi(2n+3)-1, where phi is the Euler totient function. - Charles R Greathouse IV, Sep 12 2012

EXAMPLE

{1, 5, 7, 11} are coprime to 12, so a(10) = 4.

{1, 2, 3, 4} are coprime to 5, so a(3) = 3 since 2 is excluded.

MATHEMATICA

Array[EulerPhi[# + 2] - Boole[OddQ@ #] &, 70] (* Michael De Vlieger, Jan 20 2020 *)

PROG

(C) See Cano link.

(PARI) a(n)=eulerphi(n+2)-n%2 \\ Charles R Greathouse IV, Sep 12 2012

CROSSREFS

Sequence in context: A067316 A210221 A232113 * A267807 A127433 A055573

Adjacent sequences:  A216472 A216473 A216474 * A216476 A216477 A216478

KEYWORD

nonn,easy

AUTHOR

R. J. Cano, Sep 11 2012

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 December 5 11:48 EST 2020. Contains 338947 sequences. (Running on oeis4.)