[seqfan] Numbers of the Form 2^j (mod 10^k)

[Paul D. Hanna]

     Given only the last 5 (say) digits of a large integer N, 
how can you determine if N is NOT some power of 2? 
That is, 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 were not in this sequence, 
then N would not be a power of 2. 
 
Along this line of thought, the following 4 questions arise when 
we let the number of known digits be any positive integer. 
   
(1) What numbers are of the form:  
  2^j (mod 10^k)  
where j and k are any positive integers? 
  
The sequence begins (please verify):
{2,4,6,8,
12,16,24,28,32,36,44,48,52,56,64,68,72,76,84,88,92,96,
104,112,128,136,144,152,168,176,184,192,208,216,224,232,248,
256,264,272,288,296,304,312,328,336,344,352,368,376,384,392,
408,416,424,432,448,456,464,472,488,496,504,512,528,536,544,
552,568,576,584,592,608,616,624,632,648,656,664,672,688,696,
704,712,728,736,744,752,768,776,784,792,808,816,824,832,848,
856,864,872,888,896,904,912,928,936,944,952,968,976,984,992,
1008,1024,1056,1072,1088,1104,1136,1152,1168,1248,1312,1328,
1344,1376,1392,1424,1456,1488,1504,1536,1584,1616,1632,1648,
1664,1712,1744,1808,1824,1856,1888,1904,1968,1984,2016,2032,
2048,2112,2144,2176,2192,2208,2224,2256,2272,2288,2304,2336,
2352,2496,2512,2624,2656,2672,2688,2704,2736,2752,2768,2784,
2832,2848,2864,2896,2912,2928,2976,2992,3008,3056,3072,3088,
3168,3184,3216,3232,3248,3264,3296,3312,3328,3424,3472,3488,
3616,3648,3696,3712,3728,3776,3792,3808,3888,3936,3952,3968,
4032,4064,4096,4112,4224,4288,4304,4352,4368,4384,4416,4432,
4448,4464,4512,4544,4576,4592,4608,4672,4704,4784,4816,4848,
4912,4944,4992,5024,5072,5104,5136,5168,5232,5248,5264,5312,
5328,5344,5376,5408,5456,5472,5504,5536,5552,5568,5584,5664,
5696,5712,5728,5744,5792,5808,5824,5856,5872,5904,5952,5984,
6016,6096,6112,6128,6144,6176,6256,6336,6352,6368,6384,6416,
6432,6448,6464,6496,6528,6544,6592,6608,6624,6656,6736,6848,
6864,6896,6944,6976,7056,7152,7184,7216,7232,7296,7376,7392,
7408,7424,7456,7472,7536,7552,7568,7584,7616,7632,7664,7728,
7776,7792,7856,7872,7904,7936,7952,8048,8064,8128,8176,8192,
8208,8224,8272,8304,8368,8432,8448,8528,8576,8592,8608,8688,
8704,8736,8768,8784,8816,8832,8864,8896,8928,8976,9024,9088,
9104,9136,9152,9184,9216,9264,9296,9344,9392,9408,9488,9552,
9568,9632,9648,9696,9744,9776,9824,9872,9888,9936,9968,9984,....}
 
(2) Further, what is the number of terms in the above sequence having n
digits?
I think this sequence begins:  {4,18,90,264,...?} for n=1,2,3,4,... 
 
(3) Do there exist formulas or generating functions for any of the above
2 sequences? 
 
(4) What are the corresponding sequences in (1) and (2) for powers of 3,
that is, 
what are the numbers of the form: 3^j (mod 10^k) ? 
 
This sequence would begin:
{1,3,7,9,
21,23,27,29,41,43,47,49,61,63,67,69,81,83,87,89, 
107,121,123,129,147,161,163,169,187,201,203,209,227,241,
243,249,267,281,283,289,307,321,323,329,347,361,363,369,...}
(are these equal to the 'evenish numbers': 
http://www.research.att.com/projects/OEIS?Anum=A045797 ?).
 
and the number of terms with n digits is: 
{4,16,...?}.
Please extend and verify.
  
I do not believe that these sequences are yet in the OEIS 
(except perhaps sequence in (4) above). 
If someone finds these sequences of interest, feel free to submit.
 
Thanks,
     Paul
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20040827/17c30f44/attachment.htm>