A253719 Least k>0 such that n AND (n^k) <= 1, where AND denotes the bitwise AND operator.

1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 2, 4, 2, 4, 4, 2, 2, 2, 2, 2, 3, 6, 5, 4, 2, 4, 2, 8, 3, 8, 5, 2, 2, 2, 2, 2, 2, 2, 3, 6, 2, 2, 4, 12, 2, 4, 4, 4, 2, 4, 2, 10, 3, 14, 6, 8, 2, 8, 6, 16, 3, 16, 6, 2, 2, 2, 2, 2, 2, 2, 4, 2, 3, 4, 4, 4, 2, 4, 4, 6, 2, 2, 5, 8, 4

Offset

0,3

Comments

This sequence is well defined: for any n such that n < 2^m:

- If n is even, then n^m = 0 mod 2^m, hence n AND (n^m) = 0, and a(n) <= m,

- If n is odd, then n^phi(2^m) = 1 mod 2^m according to Euler's totient theorem, hence n AND (n^phi(2^m)) = 1, and a(n) <= phi(2^m).

a(2*(2^m-1)) = m+1 for any m>=0. - Paul Tek, May 03 2015

Links

Paul Tek, Table of n, a(n) for n = 0..100000

Example

11 AND (11^1) = 11,
11 AND (11^2) = 9,
11 AND (11^3) = 3,
11 AND (11^4) = 1,
hence a(11)=4.

Prog

(PARI) a(n) = my(k=1, nk=n); while (bitand(n, nk)>1, k=k+1; nk=nk*n); return (k)

Crossrefs

Cf. A224694.

Sequence in context: A217619 A187186 A259651 * A081147 A236103 A278293

Adjacent sequences: A253716 A253717 A253718 * A253720 A253721 A253722

Keyword

nonn,base

Author

Paul Tek, May 02 2015

Status

approved