

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 LucasLehmer 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 8tuples of odd integers into singlebyte 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 "offsetvalue" pairs for sequence A216475
R. J. Cano, C program source code for generating this sequence
R. J. Cano, A stub of the bfile 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



