login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

a(n) = (Sum_{k = 1..n-1} k*a(k)) (mod n) with a(1) = 1.
0

%I #14 May 18 2024 14:56:50

%S 1,1,0,3,0,3,5,4,1,9,1,6,9,7,2,15,2,9,13,10,3,21,3,12,17,13,4,27,4,15,

%T 21,16,5,33,5,18,25,19,6,39,6,21,29,22,7,45,7,24,33,25,8,51,8,27,37,

%U 28,9,57,9,30,41,31,10,63,10,33,45,34,11,69,11,36,49,37,12,75,12,39,53,40

%N a(n) = (Sum_{k = 1..n-1} k*a(k)) (mod n) with a(1) = 1.

%C Compare with A066910.

%C More generally, define a sequence {a(n, s) : n >= 1} with starting parameter s by a(n, s) = (Sum_{k = 1..n-1} k*a(k, s)) (mod n) with a(1, s) = s. The sequence {a(n, s)} is conjectured to be one of 3 types as illustrated by the following examples for s in [1..100].

%C 1) It is easy to verify that the sequence {a(n, 8)} = {8, 0, 2, 2, 2, 2, ...} becomes constant at n = 3 and the sequence {a(n, 38)} = {38, 0, 2, 0, 4, 4, 4, ...} becomes constant at n = 5.

%C 2) For s in {2, 5, 20, 21, 22, 31, 33, 34, 35, 36, 40, 42, 60, 65, 85, 87, 88, 92, 93, 97, 98, 100} the sequence {a(n, s)} appears to be quasipolynomial in n with 6 constituent polynomials of degree 1.

%C 3) For the remaining values of s <= 100, the sequence {a(n, s)} appears to be an eventually periodic sequence with period 6, so again quasipolynomial in n with 6 constituent polynomials of degree 0. For example, an easy induction argument shows that {a(n, 3)} = {3, 1, 2, 3, 3, 2, 1, 1, 2, 3, 3, 2, 1, 1, 2, 3, 3, 2, 1, ...} has period 6 starting at n = 2.

%H MathOverflow, <a href="http://mathoverflow.net/questions/191518">Mod sequences that seem to become constant</a>

%F a(n) is quasipolynomial in n (proved by induction): a(6*n) = 3*n for n >= 1, and for n >= 0, a(6*n+1) = 4*n + 1, a(6*n+2) = 3*n + 1, a(6*n+3) = n, a(6*n+4) = 6*n + 3 and a(6*n+5) = n.

%F G.f.: A(x) = x*(x^8 + 4*x^7 + 4*x^6 + 2*x^5 + x^4 + 2*x^3 + x^2 + 2*x + 1)/((x + 1)^2*(x - 1)^2*(x^2 - x + 1)*(x^2 + x + 1)^2).

%p a := proc(n, s) option remember; if n = 1 then s else irem(add(k*a(k, s), k = 1 .. n-1), n) end if; end proc:

%p seq(a(n, 1), n = 1..80);

%t CoefficientList[Series[x(x^8 + 4*x^7 + 4*x^6 + 2*x^5 + x^4 + 2*x^3 + x^2 + 2*x + 1)/((x + 1)^2*(x - 1)^2*(x^2 - x + 1)*(x^2 + x + 1)^2),{x,0,80}],x] (* _Stefano Spezia_, May 18 2024 *)

%o (PARI) lista(nn) = my(v=vector(nn)); v[1]=1; for(n=2, nn, v[n]=sum(k=1, n-1, k*v[k])%n); v; \\ _Michel Marcus_, May 18 2024

%Y Cf. A066910, A073117, A094405, A074482, A117846, A253387.

%K nonn,easy

%O 1,4

%A _Peter Bala_, May 15 2024