Almost the number of divisors of n+1

[Andrew Plewe]

Marc said:

Some random and rather vague ideas:

1. I faintly recall seeing something about algorithms for
factoring n involving properties of n-1 (I mean besides
the obvious connection to "Fermat's little theorem").
Perhaps in Knuth's TAOCP? 



I have that book in front of me right now; he demonstrates how to use the
properties of n-1 to verify primality (pg. 375, in vol. 2, 2nd edition)
after applying Fermat's theorm. 

One a similar note, one could also try to solve:

n - 1 = a mod (a + 1) (or, more generally, n - x = a mod (a + x))

in which case a + 1 (or x) will be a factor of n, but I don't think that's a
particularly practical method -- finding a "mod difference" for n - x seems
to be just as hard as factoring n, even if you know the factors of n - x.

	-Andrew Plewe-

-----Original Message-----
From: Marc LeBrun [mailto:mlb at well.com] 
Sent: Tuesday, November 21, 2006 3:26 PM
To: seqfan at ext.jussieu.fr
Subject: Re: Almost the number of divisors of n+1

 >  a(n) is the number of divisors of (n+1)
 > Have you ever seen closely-related sequences like that one?

Some random and rather vague ideas:

1. I faintly recall seeing something about algorithms for
factoring n involving properties of n-1 (I mean besides
the obvious connection to "Fermat's little theorem").
Perhaps in Knuth's TAOCP?

2. It sounds like you might have a case where the relationship
you're seeing, a(n) ~ d(n), is actually a first approximation
to some identity like

   a(n) = d(n) + F1(n) + F2(n) + ...

where the Fk depend on the factor structure of n or something.
So perhaps you might try to "take out" the d(n) and then look
further into the "error" and see what you can guess about how
the Fk's specifically vary with primes, highly composites, etc.
For example you might try "fitting" a(n) with Moebius-style sums.

3. There's some rather surprising known relationships involving
divisors--my favorite is one of Legendre's that is basically an
identity found by expanding elliptic functions in power series.
This suggests that you might want to express your relationships
as generating functions and see what emerges.

4. Sometimes there is simple underlying "combinatorial machinery".
For example I was once puzzled by some coefficients that turned
out to be formed by taking each divisor of n, *adding 1*, and then
multiplying them all together!  It took me a while to see that's
algebraically identical to summing the products of every possible
subset of the divisors.  But the "add 1" way of expressing this
was totally opaque, whereas the "every subset" explained them.

Happy hunting!