login
A279047
Number k of modular reductions at which the recurrence relation x(i+1) = x(0) mod x(i) terminates with x(k) = 1, where x(0) = prime(n+1), x(1) = prime(n).
0
1, 2, 2, 4, 2, 2, 2, 4, 4, 2, 2, 2, 2, 4, 5, 6, 2, 2, 4, 2, 2, 4, 4, 2, 2, 2, 4, 2, 2, 2, 4, 4, 2, 5, 2, 2, 2, 4, 5, 6, 2, 2, 2, 2, 2, 3, 4, 4, 2, 2, 6, 2, 2, 4, 5, 4, 2, 2, 2, 2, 4, 5, 4, 2, 2, 5, 2, 6, 2, 2, 6, 4, 2, 2, 4, 4, 4, 2, 2, 7, 2, 2, 2, 2, 4, 4, 2, 2, 2, 4, 8, 5, 4, 3, 4, 4, 3, 2, 2, 2, 4, 5, 4, 2, 2, 6, 5, 6
OFFSET
1,2
COMMENTS
x(i) is a strictly decreasing sequence of nonnegative integers by definition of modular reduction. So at some point x(t) = 0. Let j be the previous positive value, i.e., x(t-1) = j. Then as x(0) mod j = prime(n+1) mod j = x(t) = 0, j|prime(n+1). Since j < prime(n+1), j = 1.
EXAMPLE
For n=4, x(0) = p(5) = 11, x(1) = p(4) = 7. 11 mod 7 = 4 ==> 11 mod 4 = 3 ==> 11 mod 3 = 2 ==> 11 mod 2 = 1. Since there are four modular reductions, a(4) = 4.
PROG
(SageMath)
A = []
q = 1
for i in range(100):
q = next_prime(q)
p = next_prime(q)
r = p%q
ctr = 1
while r!=1:
r = p%r
ctr += 1
A.append(ctr)
print(A)
CROSSREFS
KEYWORD
nonn
AUTHOR
Adnan Baysal, Dec 04 2016
STATUS
approved