cp's OEIS Frontend

A322850 Number of times 2^k for k < n-1 appears as a substring within 2^n.

%I A322850 #27 Feb 11 2019 19:48:44
%S A322850 0,0,0,0,1,1,1,3,1,2,3,3,1,3,4,3,0,3,5,5,3,3,4,4,5,4,5,6,4,3,6,8,4,4,
%T A322850 6,3,3,5,5,6,5,6,7,5,9,9,6,8,6,7,9,9,3,5,10,5,3,11,10,8,8,6,11,7,10,
%U A322850 13,10,10,8,7,13,16,12,9,13,8,9,16,8,9,12,15,14,7,14,9
%N A322850 Number of times 2^k for k < n-1 appears as a substring within 2^n.
%F A322850 a(n) >= A322849(n), for n >= 4.
%e A322850 n =  0, a(n) = 0, 2^n =     1 - no solutions;
%e A322850 n =  1, a(n) = 0, 2^n =     2 - no solutions;
%e A322850 n =  2, a(n) = 0, 2^n =     4 - no solutions;
%e A322850 n =  3, a(n) = 0, 2^n =     8 - no solutions;
%e A322850 n =  4, a(n) = 1, 2^n =    16 - solution is 1;
%e A322850 n =  5, a(n) = 1, 2^n =    32 - solution is 2;
%e A322850 n =  6, a(n) = 1, 2^n =    64 - solution is 4;
%e A322850 n =  7, a(n) = 3, 2^n =   128 - solutions are 1,2,8;
%e A322850 n = 14, a(n) = 4, 2^n = 16384 - solutions are 1,4,8,16;
%e A322850 n = 15, a(n) = 3, 2^n = 32768 - solutions are 2,8,32;
%e A322850 n = 16, a(n) = 0, 2^n = 65536 - no solutions.
%t A322850 Array[If[# < 4, Total@ DigitCount[2^#, 10, 2^Range[0, Min[# - 1, 3]]], Total@ DigitCount[2^#, 10, {1, 2, 4, 8}]] &, 85, 0] (* _Michael De Vlieger_, Dec 31 2018 *)
%o A322850 (Python 3.7)
%o A322850 import re
%o A322850 results = []
%o A322850 start_n = 0
%o A322850 N = 100
%o A322850 compare_list = []   # Store powers up to n-1
%o A322850 current_num = int(pow(2, start_n-1))    # Calculate (n-1) power. Convert to integer for better precision
%o A322850 for n in range(start_n, N):
%o A322850     if n == 0:
%o A322850         current_num = 1
%o A322850     else:
%o A322850         current_num += current_num
%o A322850     current_string = str(current_num)
%o A322850     count = 0
%o A322850     for test_str in compare_list:
%o A322850         count += len(re.findall(test_str, current_string))
%o A322850     compare_list.append(current_string)
%o A322850     results.append(count)
%o A322850     a=1
%o A322850 print(results)
%o A322850 (PARI) isp2(n) = (n==1) || (n==2) || (ispower(n,,&k) && (k==2));
%o A322850 a(n) = {my(d=digits(2^n), nb = 0); for (i=1, #d-1, for (j=1, #d-i+1, my(nd = vector(i, k, d[j+k-1])); if (nd[1] != 0, nb += isp2(fromdigits(nd))););); nb;} \\ _Michel Marcus_, Dec 30 2018
%Y A322850 Cf. A065712 (1), A065710 (2), A065715 (4), A065719 (8).
%Y A322850 Cf. A322849.
%K A322850 base,nonn
%O A322850 0,8
%A A322850 _Gaitz Soponski_, Dec 28 2018