A320562 Irregular table read by rows: T(n,k) is the smallest m such that m^m == 2*k + 1 (mod 2^n), 0 <= k <= 2^(n-1) - 1.

1, 1, 3, 1, 3, 5, 7, 1, 11, 5, 7, 9, 3, 13, 15, 1, 27, 21, 23, 9, 19, 29, 15, 17, 11, 5, 7, 25, 3, 13, 31, 1, 27, 21, 55, 9, 19, 29, 47, 17, 11, 37, 39, 25, 3, 45, 31, 33, 59, 53, 23, 41, 51, 61, 15, 49, 43, 5, 7, 57, 35, 13, 63

Offset: 1

Author

Jianing Song, Oct 15 2018

Keywords

• nonn
• tabf

Comments

The sequence {k^k mod 2^n} has period 2^n. The n-th row contains 2^(n-1) numbers, and is a permutation of the odd numbers below 2^n.

Note that the first 5 rows are the same as those in A320561, but after that they differ.

For all n, k we have v(T(n,k)-1, 2) = v(k, 2) + 1 and v(T(n,k)+1, 2) = v(k+1, 2) + 1, where v(k, 2) = A007814(k) is the 2-adic valuation of k. [Revised by Jianing Song, Nov 24 2018]

For n >= 3, T(n,k) = 2*k + 1 iff k is divisible by 2^floor((n-1)/2) or k = 2^(n-2) - 1 or k = 2^(n-1) - 1.

T(n,k) is the multiplicative inverse of A321906(n,k) modulo 2^n. - Jianing Song, Nov 24 2018

Examples

			Table starts
1,
1, 3,
1, 3, 5, 7,
1, 11, 5, 7, 9, 3, 13, 15,
1, 27, 21, 23, 9, 19, 29, 15, 17, 11, 5, 7, 25, 3, 13, 31,
1, 27, 21, 55, 9, 19, 29, 47, 17, 11, 37, 39, 25, 3, 45, 31, 33, 59, 53, 23, 41, 51, 61, 15, 49, 43, 5, 7, 57, 35, 13, 63,
...
		

Links

• Jianing Song, Table of n, a(n) for n = 1..8191 (Rows n=1..13)

Crossrefs

Cf. A007814.

{x^x} and its inverse: A320561 & this sequence.

{x^(-x)} and its inverse: A321901 & A321904.

{x^(1/x)} and its inverse: A321902 & A321905.

{x^(-1/x)} and its inverse: A321903 & A321906.

Programs

Mathematica

Table[Block[{m = 1}, While[PowerMod[m, m, 2^n] != Mod[2 k + 1, 2^n], m++]; m], {n, 6}, {k, 0, 2^(n - 1) - 1}] // Flatten (* Michael De Vlieger, Oct 22 2018 *)

PARI

T(n,k) = my(m=1); while(Mod(m, 2^n)^m!=2*k+1, m+=2); m
tabf(nn) = for(n=1, nn, for(k=0, 2^(n-1)-1, print1(T(n, k), ", ")); print);

Formula

For given n >= 2 and 0 <= k <= 2^(n-2) - 1, T(n,k) = T(n-1,k) if T(n-1,k)^T(n-1,k) == 2*k + 1 (mod 2^n), otherwise T(n-1,k) + 2^(n-1); for 2^(n-2) <= k <= 2^(n-1) - 1, T(n,k) = T(n,k-2^(n-2)) + 2^(n-1) if T(n,k) < 2^(n-1), otherwise T(n,k-2^(n-2)) - 2^(n-1).

T(n,k) = 2^n - A321904(n,2^(n-1)-1-k). - Jianing Song, Nov 24 2018