|
%I #16 May 03 2015 17:54:06
%S 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,
%T 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,
%U 2,2,2,2,4,2,3,4,4,4,2,4,4,6,2,2,5,8,4
%N Least k>0 such that n AND (n^k) <= 1, where AND denotes the bitwise AND operator.
%C This sequence is well defined: for any n such that n < 2^m:
%C - If n is even, then n^m = 0 mod 2^m, hence n AND (n^m) = 0, and a(n) <= m,
%C - 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).
%C a(2*(2^m-1)) = m+1 for any m>=0. - _Paul Tek_, May 03 2015
%H Paul Tek, <a href="/A253719/b253719.txt">Table of n, a(n) for n = 0..100000</a>
%e 11 AND (11^1) = 11,
%e 11 AND (11^2) = 9,
%e 11 AND (11^3) = 3,
%e 11 AND (11^4) = 1,
%e hence a(11)=4.
%o (PARI) a(n) = my(k=1, nk=n); while (bitand(n, nk)>1, k=k+1; nk=nk*n); return (k)
%Y Cf. A224694.
%K nonn,base
%O 0,3
%A _Paul Tek_, May 02 2015
|
