A109434 -id:A109434 - cp's OEIS frontend

A109433 Triangle read by rows: T(n,m) = number of binary numbers n+1 digits long which have m 1's as a substring.

1, 2, 1, 4, 2, 1, 8, 5, 2, 1, 16, 11, 5, 2, 1, 32, 24, 12, 5, 2, 1, 64, 51, 27, 12, 5, 2, 1, 128, 107, 60, 28, 12, 5, 2, 1, 256, 222, 131, 63, 28, 12, 5, 2, 1, 512, 457, 282, 140, 64, 28, 12, 5, 2, 1, 1024, 935, 601, 307, 143, 64, 28, 12, 5, 2, 1, 2048, 1904, 1270, 666, 316, 144

Offset: 0

Robert G. Wilson v, Jun 27 2005

			T(4,2)=11 because of the sixteen binary digits which are 5 long, {10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111}, 11 have "11" as a substring.
Triangle begins:
n\m
0 1 0 0 0 0 0 0 0 0 0
1 2 1 0 0 0 0 0 0 0 0
2 4 2 1 0 0 0 0 0 0 0
3 8 5 2 1 0 0 0 0 0 0
4 16 11 5 2 1 0 0 0 0 0
5 32 24 12 5 2 1 0 0 0 0

First column = A000079 = Powers of 2, the second column = A027934 = number of compositions of n with at least one even part and the last column = A045623 = number of 1's in all compositions of n+1.

Cf. A000079, A027934, A045623, A109434, A109435.

T[n_, m_] := Length[ Select[ StringPosition[ #, ToString[(10^m - 1)/9]] & /@ Table[ ToString[ FromDigits[ IntegerDigits[i, 2]]], {i, 2^n, 2^(n + 1) - 1}], # != {} &]]; Flatten[ Table[ T[n, m], {n, 0, 11}, {m, n + 1}]]

A109436 Triangle of numbers: row n gives the elements along the subdiagonal of A109435 that connects 2^n with (n+2)*2^(n-1).

Original entry on oeis.org

0, 0, 1, 1, 2, 3, 4, 7, 8, 8, 15, 19, 20, 16, 31, 43, 47, 48, 32, 63, 94, 107, 111, 112, 64, 127, 201, 238, 251, 255, 256, 128, 255, 423, 520, 558, 571, 575, 576, 256, 511, 880, 1121, 1224, 1262, 1275, 1279, 1280, 512, 1023, 1815, 2391, 2656, 2760, 2798, 2811

Offset: 0

Robert G. Wilson v, Jun 28 2005

In the limit of row number n->infinity, the differences of the n-th row of the table, read from right to left, are 1, 4, 13, 38, 104,... = A084851.

			The triangle A109435 begins
    1;
    2,   1;
    4,   3,   1;
    8,   7,   3,   1;
   16,  15,   8,   3,   1;
   32,  31,  19,   8,   3,   1;
   64,  63,  43,  20,   8,   3,   1;
  128, 127,  94,  47,  20,   8,   3,   1;
If we read this triangle starting at 2^n in its first column along its n-th subdiagonal up to the first occurrence of (n+2)*2^(n-1), we get row n of the current triangle, which begins:
   0,   0;
   1,   1;
   2,   3;
   4,   7,   8;
   8,  15,  19,  20;
  16,  31,  43,  47,  48;
  32,  63,  94, 107, 111, 112;

Cf. A109435, A001792, A109434, A084851.

T[n_, m_] := Length[ Select[ StringPosition[ #, StringDrop[ ToString[10^m], 1]] & /@ Table[ ToString[ FromDigits[ IntegerDigits[i, 2]]], {i, 2^n, 2^(n + 1) - 1}], # != {} &]]; Flatten[ Table[ T[n + i, i], {n, 0, 9}, {i, 0, n}]]

Edited by R. J. Mathar, Nov 17 2009

A343494 Numbers k such that tau(k) and tau(k+1) are both prime, where tau is the number of divisors function.

Original entry on oeis.org

2, 3, 4, 16, 65536

Offset: 1

Claude H. R. Dequatre, Apr 17 2021

Considering the first 10^8 positive integers, we note the following: only five of them meet the definition; the first two (2,3) are prime and the next three (4, 16 and 65536) are perfect squares (4 = 2^2, 16 = 4^2 and 65536 = 256^2).
Open questions: are there any other terms greater than 65536? If yes, are they all composite numbers and more specifically perfect squares?
From Jon E. Schoenfield, Apr 19 2021: (Start)
a(6), if it exists, is at least 2^(2^(2^33)). Proof:
Every number having a prime number of divisors is of the form p^e where p is a prime and the exponent e is a nonnegative integer such that e+1 is prime, so we can write k = p^j, k+1 = q^m, and p^j + 1 = q^m, where both j+1 and m+1 are prime.
Either k or k+1 must be even, so either p or q must be 2.
Suppose q=2. We have p^j + 1 = 2^m, so p^j = 2^m - 1. m cannot be 1, since that would mean p^j = 1 (impossible), and m+1 is prime, so m is an even number. Let m = 2*v. Then p^j = 2^(2*v) - 1 = (2^v - 1)*(2^v + 1): two factors differing by exactly two, and both odd. The only way their product can be a prime power (i.e., p^j) is if they are 1 and 3, so p^j = 1*3 = 3, i.e., k=3; this is a(2), the only odd term in the sequence.
Now suppose p=2. We have 2^j + 1 = q^m, so 2^j = q^m - 1. If m > 1, then since m+1 is prime, m is an even number. Let m = 2*v. Then 2^j = q^(2*v) - 1 = (q^v - 1)*(q^v + 1): again, two factors differing by exactly two, but this time, both are even. The only way their product can be a power of 2 (i.e., 2^j) is if q^v - 1 and q^v + 1 are 2 and 4, so we have 2^j = 2*4 = 8. But tau(8) = 4 (not a prime).
So if p=2, we must have m=1, and thus 2^j + 1 = q. But 2^j + 1 cannot be prime unless j is a power of 2, so we have k = 2^j = 2^(2^u) for some nonnegative integer u such that both tau(k) = tau(2^(2^u)) = 2^u + 1 and k+1 = 2^(2^u) + 1 are prime. However, tau(k) = 2^u + 1 is prime only when it is either 2 (which occurs at u=0, i.e., at k = 2^(2^0) = 2^1 = 2, which is a(1)) or a Fermat prime (cf. A019434), i.e., a prime of the form 2^(2^t)+1 for some nonnegative integer t. So, other than a(1)=2, all even terms k must satisfy k = 2^j and tau(k) = tau(2^j) = j+1 = 2^(2^t)+1, i.e., j=2^(2^t), so k = 2^j = 2^(2^(2^t)), such that tau(k) = 2^(2^t)+1 is a Fermat prime. Only 5 Fermat primes are known: 3, 5, 17, 257, and 65537; these are 2^(2^t)+1 where t = 0, 1, 2, 3, and 4. It is known (see comments at A109434) that 2^(2^t)+1 is composite for all t in 5..32, so since tau(k) must be a prime, t cannot be in 5..32; also, since k+1 must be a prime, t cannot be in 3..5 (these would result in k+1 = 2^(2^8)+1, 2^(2^16)+1, and 2^(2^32)+1, respectively). Consequently, if k is an even term > a(1)=2, we must have k = 2^(2^(2^t)) with t in 0..2 or t >= 33:
.
   t  k = 2^(2^(2^t))       k+1         tau(k) = 2^(2^t)+1
  --  ---------------  -------------  ----------------------
   0       4 (= a(3))      5 (prime)           3 (prime)
   1      16 (= a(4))     17 (prime)           5 (prime)
   2   65536 (= a(5))  65537 (prime)          17 (prime)
   3      2^(2^8)       (composite)          257 (prime)
   4      2^(2^16)      (composite)        65537 (prime)
   5      2^(2^32)      (composite)    2^(2^5)+1 (composite)
   6      2^(2^64)          (?)        2^(2^6)+1 (composite)
   .         .              (?)                  (composite)
   .         .              (?)                  (composite)
   .         .              (?)                  (composite)
  32    2^(2^(2^32))        (?)       2^(2^32)+1 (composite)
  33    2^(2^(2^33))        (?)       2^(2^33)+1     (?)
.
So a(6), if it exists, must be at least 2^(2^(2^33)). (End)

			16 is a term because tau(16) = 5 and tau(17) = 2 and 5 and 2 are prime.
147 is not a term because tau(147) = 6 and tau(148) = 6 and 6 is not prime.
157 is not a term because tau(157) = 2 and tau(158) = 4 and 2 is prime but not 4.

Cf. A000005, A000040, A009087.

Select[Range[1000000], PrimeQ[DivisorSigma[0, #]] && PrimeQ[DivisorSigma[0, #+1]] &] (* Vaclav Kotesovec, Apr 19 2021 *)

for(k=1,1e8,if(isprime(numdiv(k)) && isprime(numdiv(k+1)),print1(k", ")))

cp's OEIS Frontend

A109433 Triangle read by rows: T(n,m) = number of binary numbers n+1 digits long which have m 1's as a substring.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A109436 Triangle of numbers: row n gives the elements along the subdiagonal of A109435 that connects 2^n with (n+2)*2^(n-1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A343494 Numbers k such that tau(k) and tau(k+1) are both prime, where tau is the number of divisors function.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI