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, 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
KEYWORD
nonn,easy
AUTHOR
R. J. Cano, Sep 11 2012
STATUS
approved