A104039 -id:A104039 - cp's OEIS frontend

A380500 Table T(n,k) = phi(phi(prime(n)^k)), n >= 1, k >= 0, read by upwards antidiagonals, where phi = A000010.

1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 8, 6, 4, 1, 4, 12, 40, 18, 8, 1, 4, 40, 84, 200, 54, 16, 1, 8, 48, 440, 588, 1000, 162, 32, 1, 6, 128, 624, 4840, 4116, 5000, 486, 64, 1, 10, 108, 2176, 8112, 53240, 28812, 25000, 1458, 128, 1, 12, 220, 2052, 36992, 105456, 585640, 201684, 125000, 4374, 256

Offset: 1

Michael De Vlieger, Feb 04 2025

For n >= 2, k >= 1, T(n,k) is the number of primitive roots of prime(n)^k.

			Table begins as follows:
n\k  0   1     2      3       4        5          6           7
---------------------------------------------------------------
1:   1   1     1      2       4        8         16          32
2:   1   1     2      6      18       54        162         486
3:   1   2     8     40     200     1000       5000       25000
4:   1   2    12     84     588     4116      28812      201684
5:   1   4    40    440    4840    53240     585640     6442040
6:   1   4    48    624    8112   105456    1370928    17822064
7:   1   8   128   2176   36992   628864   10690688   181741696

Michael De Vlieger, Table of n, a(n) for n = 1..11476 (rows n = 1..150, flattened).

Cf. A000010, A000040, A001248, A008330, A010554, A046144, A104039, A246655.

Table[EulerPhi[EulerPhi[Prime[#]^k]] &[n - k + 1], {n, 0, 10}, {k, 0, n}] // Flatten

T(n,k) = A010554(prime(n)^k) = A046144(prime(n)^k).
T(n,0) = 1.
T(n,1) = phi(prime(n)-1) = A008330(n).
T(n,2) = (prime(n)-1) * phi(prime(n)-1)
       = (prime(n)-1)^2 * Product_{q|(prime(n)-1)} 1-1/q, prime q.
       = A104039(n).
For k > 1, T(n,k) = prime(n)^(k-2) * A104039(n).
T(n,2) > prime(n) for n > 2.
T(n,k) < prime(n)^k for all n and for k > 0.

A213272 Costas arrays such that the terms in each row of the difference table are unique modulo n.

Original entry on oeis.org

1, 2, 0, 8, 0, 12, 0, 0, 0, 40, 0, 48, 0, 0, 0, 128, 0, 108, 0, 0, 0, 220, 0, 0, 0, 0, 0, 336, 0

Offset: 1

Joerg Arndt, Jun 08 2012

Permutations of n elements such that each row in the difference table consists of pairwise distinct elements, even when taken modulo n (see example).
For n<=29 the nonzero terms a(n) appear for n in A006093 (primes minus 1) and a(n)=A002618(n) (n*phi(n)); omitting the zeros we obtain A104039 (number of primitive roots modulo (p(n))^2, where p(n) is n-th prime).
A002618(n) divides a(n) for all n, since (treating elements as integers modulo n) adding or subtracting a constant from each element or multiplying each element by an integer coprime to n preserves distinctness of all values modulo n. - Charlie Neder, May 26 2019

			The permutation (10, 9, 2, 8, 6, 1, 3, 7, 4, 5) corresponds to a Costas array:
  10  9  2  8  6  1  3  7  4  5  (Permutation: p(1), p(2), p(3), ..., p(n) )
  -1 -7  6 -2 -5  2  4 -3  1     (step-1 differences: p(2)-p(1), p(3)-p(2), ... )
  -8 -1  4 -7 -3  6  1 -2        (step-2 differences: p(3)-p(1), p(4)-p(2), ... )
  -2 -3 -1 -5  1  3  2           (step-3 differences: p(4)-p(1), p(5)-p(2), ... )
  -4 -8  1 -1 -2  4              ( etc. )
  -9 -6  5 -4 -1
  -7 -2  2 -3
  -3 -5  3
  -6 -4
  -5
The values in each row are unique also modulo n=10:
  10 9 2 8 6 1 3 7 4 5  (Permutation: p(1), p(2), p(3), ..., p(n) )
   9 3 6 8 5 2 4 7 1    (step-1 differences: p(2)-p(1), p(3)-p(2), ... )
   2 9 4 3 7 6 1 8      (step-2 differences: p(3)-p(1), p(4)-p(2), ... )
   8 7 9 5 1 3 2        (step-3 differences: p(4)-p(1), p(5)-p(2), ... )
   6 2 1 9 8 4          ( etc. )
   1 4 5 6 9
   3 8 2 7
   7 5 3
   4 6
   5

Scott Rickard, costasarrays.org (information and papers about Costas arrays). [broken link?]
Wikipedia, Costas array.

Cf. A008404 (Costas arrays), A213270 (Costas arrays that are involutions), A213271 (Costas arrays that are derangements), A213338 (Costas arrays that are cyclic), A213339 (Costas arrays that are connected).

cp's OEIS Frontend

A380500 Table T(n,k) = phi(phi(prime(n)^k)), n >= 1, k >= 0, read by upwards antidiagonals, where phi = A000010.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula