cp's OEIS Frontend

A381319 Order of linear recurrence with constant coefficients of solutions of k satisfying k^(n-1) == 1 (mod n^2) for a given n.

%I A381319 #36 Apr 10 2025 08:37:24
%S A381319 2,3,2,5,2,7,2,3,2,11,2,13,2,5,2,17,2,19,2,5,2,23,2,5,2,3,4,29,2,31,2,
%T A381319 5,2,5,2,37,2,5,2,41,2,43,2,9,2,47,2,7,2,5,4,53,2,5,2,5,2,59,2,61,2,5,
%U A381319 2,17,6,67,2,5,4,71,2,73,2,5,4,5,2,79,2,3,2,83,2,17,2,5,2,89
%N A381319 Order of linear recurrence with constant coefficients of solutions of k satisfying k^(n-1) == 1 (mod n^2) for a given n.
%C A381319 For a given n, the solutions for k have the linear recurrence with constant coefficients k(m) = k(m-1) + k(m-(a(n)-1)) - k(m-a(n)), with order a(n). If a(n)=2 then the term k(m-1) appears twice and is k(m) = 2*k(m-1) - k(m-2).
%C A381319 Also, k(m) - k(m-(a(n)-1)) = n^2 = k(m-1) - k(m-a(n)), so all have nonhomogeneous linear recurrence of k(m) = k(m-(a(n)-1)) + n^2. Equivalently, k(m) = k(m-A063994(n)) + n^2, with order A063994(n). Thus, k(m) ~ (n^2 / A063994(n)) * m = (n^2 / (a(n)-1)) * m.
%H A381319 Paolo Xausa, <a href="/A381319/b381319.txt">Table of n, a(n) for n = 2..10000</a>
%F A381319 a(n) = 1 + A063994(n).
%F A381319 a(p) = p if p is prime.
%e A381319 For n=5 the congruence equation k^4 ==1 mod (5^2) has solutions of k (A056021) which satisfy k(m) = k(m-1) + k(m-4) - k(m-5), the order being 5, a(5)=5.
%e A381319 For n=9, k^8==1 mod (9^2) has solutions of k with recurrence k(m) = k(m-1) + k(m-2) - k(m-3), order 3, a(9)=3.
%t A381319 A381319[n_] := Times @@ GCD[FactorInteger[n][[All, 1]] - 1, n - 1] + 1;
%t A381319 Array[A381319, 100, 2] (* _Paolo Xausa_, Mar 05 2025 *)
%Y A381319 Cf. A063994, A056020 (n=3), A056021 (n=5), A056022 (n=7), A056024 (n=11), A056025 (n=13), A056028 (n=19), A056031 (n=23), A056034 (n=29), A056035 (n=31).
%K A381319 nonn
%O A381319 2,1
%A A381319 _Mike Sheppard_, Feb 20 2025