[seqfan] Re: Regarding Pairs Of Number-Of-Divisors

[hv at crypt.org]

hv at crypt.org wrote:
:Leroy Quet <q1qq2qqq3qqqq at yahoo.com> wrote:
::Are these sequences in the EIS?
::
::a) a(n) is the minimum positive integer k such that d(m) = n and d(m+1)=k for exactly one positive integer m. a(n) = 0 if there is no m for any k or always more than one m for all k. d(m) is the number of divisors of m.
::
::For example, let n = 4. Checking k = 1,2,3. d(m)=4 and d(m+1)=1 for no m's.
::d(m) = 4 and d(m+1) = 2 for more than one m. (d(6)=4, a(7)=2. d(10)=4, d(11)=2, for example.)
::Now we have, since d(m) = 4, m = p*q, p and q = distinct primes, or m = p^3. 
::So, letting k = 3, then m+1 must be of the form r^2, r = prime.
::So, if m = p*q, then either r is even (equals 2) and p and q are both odd, or (WLOG) p is odd and q = 2 and r is odd. m+1 = r^2 doesn't equal 4, because 4-1 doesn't have 4 divisors. So, we have r^2-1 = 2*p. 
::(r-1)*(r+1) = 2p. So, r and r+1 are twin primes, and one of them equals 2. But if r-1 = 2, then r+1 = 4, a composite.
::So, m = p^3. Since p^3+1 = r^2, then p and r have opposite parity. So, p must be 2 and r must be 3. (Again, r^2 isn't 4.)
::Therefore a(4) = 3.
::
::Also consider the related sequence:
::b) b(n) is the minimum positive integer k such that d(m) = n and d(m-1)=k for exactly one positive integer m. b(n) = 0 if there is no m for any k or always more than one m for all k.
::
::I think the sequences c and d would be interesting too, if there are an infinite number of 0's in both sequence a and b:
::
::c) Those positive integers n where a(n) = 0.
::
::d) Those positive integers n where b(n) = 0.
::
::Are these in the EIS, if they are interesting?
:
:It is worth checking the OEIS for relevant keywords, and searching through
:the recent archives - there was certainly discussion here quite recently
:about a, b such that there is a unique n with d(n)=a, d(n+1)=b.

As noted by Richard Mathar, the related discussion was about A161460.

First eight values of a(n), starting with a(1):
  2, 2, 2, 3, 2, 7, 4, 3

Corresponding values ax(n): d(ax(n))=n, d(ax(n)+1)=a(n) (or 0 if a(n)=0):
  1, 2, 3, 8, 16, 63, 64, 24

First seven values of b(n), starting with b(1):
  0, 1, 2, 7, 4, 11, 6

Corresponding values of bx(n): d(bx(n))=n, d(bx(n)+1)=b(n) (or 0 if b(n)=0):
  0, 2, 4, 65, 16, 1025, 64

b(8) is where it starts to get interesting: for b(8) = k != 0, I think we
need k prime with d(2^{k-1}+1)=8 and d(p^{k-1}+1) > 8 for all prime p > 2.

For this I think we need p^{k-1}+1 to be a polynomial with exactly 3 factors,
so we need k-1 = 2^a . q^2 for a>0 (else k is not prime), and an odd prime q.
Further, we need each of those factors to be prime for the case p=2, so 2^a+1
must be a Fermat prime, giving a in {2, 4, 8, 16} (at least with current
knowledge).

When a is 2 or 8, 2^{k-1} will be a multiple of 3 unless q == 3, but neither
d(2^18+1) nor d(2^72+1) is 8, so a is 4 or 16.

That leaves the following numbers as the candidates for b(8) up to 1e6:
  37, 101, 197, 401, 677, 5477, 8837, 13457, 15377, 17957, 21317, 42437,
  55697, 80657, 98597, 106277, 148997, 190097, 217157, 309137, 401957,
  454277, 512657, 583697

Of these, factordb rules out those up to 2^(42437-1)+1 as having too many
factors (except 2^15376+1 = P6 . P9 . N4615, which must surely also be
divisible by 65537).

So, while I cannot rule out b(8) > 0, finding a value will be hard - it
will involve establishing primality of the 3 algebraic factors of at least
a 16000-digit number.

Have I missed something? Is there some other way that b(8) can exist?

Hugo