

A184997


Number of distinct remainders that are possible when a safe prime p is divided by n (for p > 2*n+1).


1



1, 1, 1, 1, 3, 1, 5, 2, 3, 3, 9, 1, 11, 5, 3, 4, 15, 3, 17, 3, 5, 9, 21, 2, 15, 11, 9, 5, 27, 3, 29, 8, 9, 15, 15, 3, 35, 17, 11, 6, 39, 5, 41, 9, 9, 21, 45, 4, 35, 15, 15, 11, 51, 9, 27, 10, 17, 27, 57, 3, 59, 29, 15, 16, 33, 9, 65, 15, 21, 15, 69, 6, 71, 35, 15, 17, 45, 11, 77, 12
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

A number r could be a remainder of division p/n (for n > 0 and safe prime p > 2*n+1) if it satisfies two conditions:
1) r is coprime to n,
2) (r1)/2 is coprime to n (assuming r1 is even) or (n+r1)/2 is coprime to n (assuming n+r1 is even).
If one of these conditions isn't satisfied then either p or (p1)/2 isn't a prime number.
If n1 and n2 are coprime then a(n1*n2) = a(n1)*a(n2), per the Chinese remainder theorem.


LINKS

Krzysztof Ostrowski, Table of n, a(n) for n = 1..10000


EXAMPLE

a(60) = 3 as there are only three distinct remainders possible (23, 47 and 59) when dividing some safe prime p by 60. It's true for all safe primes except 5, 7 and 11.


CROSSREFS

Cf. A005385, A000010.
Sequence in context: A134033 A185051 A095026 * A094367 A092368 A225080
Adjacent sequences: A184994 A184995 A184996 * A184998 A184999 A185000


KEYWORD

nonn,mult


AUTHOR

Krzysztof Ostrowski, Apr 24 2011


STATUS

approved



