A072989 -id:A072989 - cp's OEIS frontend

A072994 Number of solutions to x^n==1 (mod n), 1<=x<=n.

1, 1, 1, 2, 1, 2, 1, 4, 3, 2, 1, 4, 1, 2, 1, 8, 1, 6, 1, 8, 3, 2, 1, 8, 5, 2, 9, 4, 1, 4, 1, 16, 1, 2, 1, 12, 1, 2, 3, 16, 1, 12, 1, 4, 3, 2, 1, 16, 7, 10, 1, 8, 1, 18, 5, 8, 3, 2, 1, 16, 1, 2, 9, 32, 1, 4, 1, 8, 1, 4, 1, 24, 1, 2, 5, 4, 1, 12, 1, 32, 27, 2, 1, 24, 1, 2, 1, 8, 1, 12, 1, 4, 3

Offset: 1

Benoit Cloitre, Aug 21 2002

More generally, if the equation a(x)*m=x has solutions, solutions are congruent to m: a(x)*7=x for x=7, 14, 21, 28, 49, 56, 63, 98, 112, ... . There are some composite values of m such that a(x)*m=x has solutions, as m=15. a(n) coincides with A009195(n) at many values of n, but not at n = 20, 30, 40, 42, 52, 60, 66, 68, 70, 78, 80, 84, 90, 100, ... . It seems also that for n large enough sum_{k=1..n} a(k) > n*log(n)*log(log(n)).

Similar (if not the same) coincidences and differences occur between A072995 and A050399. Sequence A072989 lists these indices. - M. F. Hasler, Feb 23 2014

T. D. Noe, Table of n, a(n) for n=1..10000

1, seq(nops(select(t -> t^n mod n = 1, [$1..n-1])),n=2..100); # Robert Israel, Dec 07 2014

f[n_] := (d = If[ OddQ@ n, 1, 2]; d*Length@ Select[ Range[ n/d], PowerMod[#, n, n] == 1 &]); f[1] = f[2] = 1; Array[f, 93] (* or *)
f[n_] := Length@ Select[ Range@ n, PowerMod[#, n, n] == 1 &]; f[n_] := 1 /; n<2; Array[f, 93] (* Robert G. Wilson v, Dec 06 2014 *)

A072994=n->sum(k=1,n,Mod(k,n)^n==1) \\ M. F. Hasler, Feb 23 2014

For n>0, a(A003277(n)) = 1, a(2^n) = 2^(n-1), a(A065119(n)) = A065119(n)/3.

For n>1, a(A026383(n)) = A026383(n)/5.

Corrected by T. D. Noe, May 19 2007

A072995 Least k > 0 such that the number of solutions to x^k == 1 (mod k) 1 <= x <= k is equal to n, or 0 if no such k exists.

Original entry on oeis.org

1, 4, 9, 8, 25, 18, 49, 16, 27, 50, 121, 36, 169, 98, 225, 32, 289, 54, 361, 110, 147, 242, 529, 72, 125, 338, 81, 196, 841, 0, 961, 64, 1089, 578, 1225, 108, 1369, 722, 507, 100, 1681, 0, 1849, 484, 675, 1058, 2209, 144, 343, 250, 2601, 1378, 2809

Offset: 1

Benoit Cloitre, Aug 21 2002

nonn

A072989 lists the indices for which a(n) differs from A050399(n), e.g., in n = 20, 40, 52, ... in addition to the zeros in this sequence (n = 30, 42, 66, 70, 78, 90, ...). See also A009195 vs. A072994. [Corrected and extended by M. F. Hasler, Feb 23 2014]
The sequence seems difficult to extend, as the next term a(30) is larger than 5100. However, a(32)=64, a(64)=128 and a(128)=256 can be easily calculated. It thus appears that a(2^k)=2^(k+1), for k=1,2,3,.... Is this known to be true? - John W. Layman, Aug 05 2003 -- Answer: It's true. One could have defined the sequence so that a(1)=2: then it would be true for 2^0 also. - Don Reble, Feb 23 2014
a(30), if it exists, is greater than 400000. - Ryan Propper, Sep 10 2005
a(30) doesn't exist: If N is even, and divisible by D different odd primes, but not divisible by 2^D, then a(N) doesn't exist. - Don Reble, Feb 23 2014 [This and the preceding comment refer to the former definition lacking the clause "0 if no such k exists". - Ed.]
Conjecture: a(n)=0 iff n/2 is in A061346. - Robert G. Wilson v, Feb 23 2014
[n=420 seems to be a counterexample to the above conjecture. - M. F. Hasler, Feb 24 2014]
From Robert G. Wilson v, Mar 05 2014: (Start)
Observation:
If n = 1 then a(n) = 1 by definition;
If, but not iff, n (an even number) is a member of A238367 then a(n) = 0;
If n (an even number not in A238367) is {684, 954, ...}, then a(n) = 0;
If n (an odd number) is {273, 399, 651, 741, 777, 903, ...}, then a(n) = 0;
If p is a prime [A000040] and e is its exponent, then a(p^e) = p^(e+1);
If p is a prime then a(2p^e) = 2p^(e+1);
If p is a prime then a(n) # p since the f(p)=1.
(End)
Often A072995(n) equals A050399(n). They differ at n: 20, 30, 40, 42, 52, 60, 66, 68, 70, 78, 80, 84, 90, 100, 102, 104, 110, 114, 116, 120, 126, 130, 132, ... - Robert G. Wilson v, Dec 06 2014
When A072995(n)>0 and does not equal A050399(n): 20, 40, 52, 60, 68, 80, 84, 100, 104, 116, 120, 132, 136, 140, 148, 156, 160, 164, 168, 171, 180, 200, ... - Robert G. Wilson v, Dec 06 2014
When a(n) > 1, then 2n <= a(n) <= n^2. - Robert G. Wilson v, Dec 10 2014

Robert G. Wilson v, Table of n, a(n) for n = 1..1013 (first 200 terms from Don Reble)
Robert G. Wilson v, Graph of n, a(n) for n = 1..1000

Cf. A072994.

t = Table[0, {1000}]; f[n_] := (d = If[EvenQ@ n, 2, 1]; d*Length@ Select[ Range[ n/d], PowerMod[#, n, n] == 1 &]); f[1] = 1; k = 1; While[k < 520001, If[ PrimeQ@ k, k++]; a = f@ k; If[a < 1001 && t[[a]] == 0, t[[a]] = k; Print[{a, k}]]; k++]; t (* Robert G. Wilson v, Dec 12 2014 *)

A072995(n)=(n%2||n%2^(omega(n)-1)==0)&&for(k=1,9e9,A072994(k)==n&&return(k)) \\ M. F. Hasler, Feb 23 2014

First occurrence of n in A072994.

More terms from Don Reble, Feb 23 2014

Edited, at the suggestion of Don Reble, by M. F. Hasler, Feb 23 2014

A379047 Rectangular array read by descending antidiagonals: the Type 2 runlength index array of A000002 (the Kolakoski sequence); see Comments.

Original entry on oeis.org

1, 3, 2, 5, 4, 8, 6, 11, 28, 13, 7, 16, 35, 80, 53, 9, 18, 48, 121, 217, 112, 10, 22, 62, 135, 449, 332, 305, 12, 26, 67, 175, 472, 1478, 1451, 296, 14, 31, 89, 203, 513, 1974, 1947, 1358, 1331, 15, 38, 94, 244, 812, 2101, 2683, 1920, 1827, 964, 17, 40, 107

Offset: 1

Clark Kimberling, Dec 16 2024

We begin with a definition of Type 2 runlength array, V(s), of any sequence s for which all the runs referred to have finite length:
Suppose s is a sequence (finite or infinite), and define rows of V(s) as follows:
(row 0) = s
(row 1) = sequence of last terms of runs in (row 0); c(1) = complement of (row 1) in (row 0)
For n>=2,
(row n) = sequence of last terms of runs in c(n-1); c(n) = complement of (row n) in (row n-1),
where the process stops if and when c(n) is empty for some n.
***
The corresponding Type 2 runlength index array,  The runlength index array, VI(s) is now contructed from V(s) in two steps:
(1) Let V*(s) be the array obtaining by repeating the construction of V(s) using (n,s(n)) in place of s(n).
(2) Then VI(s) results by retaining only n in V*.
Thus, loosely speaking, (row n) of VI(s) shows the indices in s of the numbers in (row n) of V(s).
The array VI(s) includes every positive integer exactly once.
***
Examples: (1) if s is monotonic, then VI(s) has just one row, the positive integers, A000027.
(2) if s = A010060 (Thue-Morse sequence), then VI(s) has exactly two rows: A003159 and A036554. The type 1 runlength index array of s also has exactly two rows: A285385 and A072989.

			Corner:
      1     3    5      6     7     9    10    12    14    15     17     19
      2     4    11    16    18    22    26    31    38    40     44     51
      8    28    35    48    62    67    89    94   107   130    150    157
     13    80   121   135   175   203   244   359   417   458    499    540
     53   217   449   472   513   812   879  1069  1272  1511   1725   1786
    112   332  1478  1974  2101  2423  2710  3282  3638  3715   3950   4145
    305  1451  1947  2683  2883  3605  3706  3827  4528  4749   4963   5076
    296  1358  1920  2590  2850  3542  5745  6400  7103  7567   7796   8346
   1331  1827  2491  2805  3437  5652  6373  7769  8265  9315  11508  11738
Using s = A000002 as an example, we have for V*(s):
(row 1) = ((1,1), (3,2), (5,1), (6,2), (7,1), (9,2), (10,1), (12,2), (14,1),...)
c(1) = ((2,2), (4,1), (8,2), (11,2), (13,1), (16,1), (18,2), (22,1), (26,2), ...)
(row 2) = ((2,2), (4,1), (11,2), (16,1), (18,2), (22,1), (26,2), (31,1), (35,2), ...)
c(2) = (8,2), (13,1), (28,1), ...)
(row 3) = (8,2), (28,1),
so that VI(s) has
(row 1) = (1,3,5,6,7,9,10,12, ...)
(row 2) = (2,4,11,16,18,22,26, ...)
(row 3) = (8,28,35,48,62,67,...)

Cf. A000002, A379046 (Type 1 array).

r[seq_] := seq[[Flatten[Position[Append[Differences[seq[[All, 1]]], 1], _?(# != 0 &)]], 2]];  (* Type 1 *)
row[0] = Prepend[Nest[Flatten[Partition[#, 2] /. {{2, 2} -> {2, 2, 1, 1}, {2, 1} -> {2, 2, 1}, {1, 2} -> {2, 1, 1}, {1, 1} -> {2, 1}}] &, {2, 2}, 24], 1]; (* A000002 *)
row[0] = Transpose[{#, Range[Length[#]]}] &[row[0]];
k = 0; Quiet[While[Head[row[k]] === List, row[k + 1] = row[0][[r[
     SortBy[Apply[Complement, Map[row[#] &, Range[0, k]]], #[[2]] &]]]]; k++]];
m = Map[Map[#[[2]] &, row[#]] &, Range[k - 1]];
p[n_] := Take[m[[n]], 12]
t = Table[p[n], {n, 1, 12}]
Grid[t]  (* array *)
w[n_, k_] := t[[n]][[k]];
Table[w[n - k + 1, k], {n, 12}, {k, n, 1, -1}] // Flatten  (* sequence *)
(* Peter J. C. Moses, Dec 04 2024 *)

cp's OEIS Frontend

A072994 Number of solutions to x^n==1 (mod n), 1<=x<=n.

Views

Author

Keywords

Comments

Links

Programs

Maple

Mathematica

PARI

Formula

Extensions

A072995 Least k > 0 such that the number of solutions to x^k == 1 (mod k) 1 <= x <= k is equal to n, or 0 if no such k exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A379047 Rectangular array read by descending antidiagonals: the Type 2 runlength index array of A000002 (the Kolakoski sequence); see Comments.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica