login
Numbers of the form 2^j (mod 10^k), where j >= 0 and k >= 1, with leading zeros suppressed.
4

%I #29 Nov 08 2017 12:25:39

%S 1,2,4,6,8,12,16,24,28,32,36,44,48,52,56,64,68,72,76,84,88,92,96,104,

%T 112,128,136,144,152,168,176,184,192,208,216,224,232,248,256,264,272,

%U 288,296,304,312,328,336,344,352,368,376,384,392,408,416,424,432,448

%N Numbers of the form 2^j (mod 10^k), where j >= 0 and k >= 1, with leading zeros suppressed.

%C Given only the last 5 (say) digits of a large integer N, can you determine whether N is not some power of 2? This is equivalent to ask which 5-digit numbers are of the form 2^j (mod 10^6) where j is any positive integer. So if the last 5 digits of N are not in this sequence, then N is not a power of 2.

%C If we have only the last k digits of an integer N, we can determine whether N is not a power of 2, if and only if the number given by those digits is divisible by 5 OR not a multiple of 2^k. - Francisco Salinas (franciscodesalinas(AT)hotmail.com), Aug 27 2004. [Edited for clarification and simplification by _M. F. Hasler_, Nov 06 2017, following discussions with _David A. Corneth_, _Peter Munn_ and _N. J. A. Sloane_. The given condition says when a k-digit number is not in this sequence. In that case we know that N is not a power of 2, otherwise, we cannot know.]

%H David A. Corneth, <a href="/A095810/b095810.txt">Table of n, a(n) for n = 1..10000</a>

%t Take[ Union[ Flatten[ Table[ PowerMod[2, j, 10^k], {j, 0, 100}, {k, 3}]]], 58] (* _Robert G. Wilson v_, Sep 11 2004 *)

%o (PARI) is(n) = valuation(n,2)>=#digits(n)&&valuation(n,5)==0 \\ _David A. Corneth_, Oct 17 2017

%o (PARI) nxt(n) = if(n==1,return(2)); q = #digits(n); n += 2^q; while(n%5==0, n += 2^q); n \\ _David A. Corneth_, Oct 17 2017

%Y Cf. A097574, A113022, A113023.

%K nonn

%O 1,2

%A _Paul D. Hanna_, Aug 30 2004

%E Additional comments from _Robert G. Wilson v_, Oct 11 2005

%E Edited by _M. F. Hasler_, Nov 06 2017