Do any integers occur in both sequences?

[Max Alekseyev]

On 7/30/07, Peter Pein <petsie at dordos.net> wrote:
> Leroy Quet schrieb:
> > I have just submitted these two interdependent sequences (So don't look
> > for them in the database yet):
> >
> >> %I A131937
> >> %S A131937 1,4,8,14,21,29,38,49,61
> >> %N A131937 a(1)=1; a(2)=4. a(n) = a(n-1) + (nth positive integer which
> >> does not occur in sequence A131938).
> >> %e A131937 A131938: 2,5,10,16,23,32,42,53,...
> >> Positive integers not in A131938: 1,3,4,6,7,8,9,11,...
> >> So A131937(8) = A131937(7) + 11 = 49.
> >> %Y A131937 A131938
> >> %O A131937 1
> >> %K A131937 ,more,nonn,
> >
> >> %I A131938
> >> %S A131938 2,5,10,16,23,32,42,53,65,78,93,109
> >> %N A131938 a(1)=2; a(2)=5. a(n) = a(n-1) + (nth positive integer which
> >> does not occur in sequence A131937).
> >> %e A131938 A131937: 1,4,8,14,21,29,...
> >> Positive integers not in A131937: 2,3,5,6,7,9,10,11,...
> >> So A131938(8) = A131938(7) + 11 = 53.
> >> %Y A131938 A131937
> >> %O A131938 1
> >> %K A131938 ,more,nonn,

[...]

> Could you please explain in detail, how you've got your sequences?

This is my PARI/GP code (for the first 50 terms) that confirms Leroy's values:

{
A=Set([1,4]); B=Set([2,5]);
a=4; na=4;
b=5; nb=3;
for(n=3,50,
  until(!setsearch(A,na),na++);
  until(!setsearch(B,nb),nb++);
  a+=nb;
  b+=na;
  A=setunion(A,[a]);
  B=setunion(B,[b]);
);
print(vecsort(eval(A)));
print(vecsort(eval(B)));
}

Here the sets A and B collect elements (as computed) of A131937 and
A131938 respectively; the variables a and b go over elements of A and
B; variables na and nb go over non-elements of A and B.

The output is:

[1, 4, 8, 14, 21, 29, 38, 49, 61, 74, 88, 103, 120, 138, 157, 177,
198, 220, 244, 269, 295, 322, 350, 379, 409, 440, 473, 507, 542, 578,
615, 653, 692, 732, 773, 816, 860, 905, 951, 998, 1046, 1095, 1145,
1196, 1248, 1302, 1357, 1413, 1470, 1528]

[2, 5, 10, 16, 23, 32, 42, 53, 65, 78, 93, 109, 126, 144, 163, 183,
205, 228, 252, 277, 303, 330, 358, 388, 419, 451, 484, 518, 553, 589,
626, 665, 705, 746, 788, 831, 875, 920, 966, 1013, 1061, 1111, 1162,
1214, 1267, 1321, 1376, 1432, 1489, 1547]

Regards,
Max



A018892 ("Number of ways to write 1/n as a sum of exactly 2 unit fractions")
has a simple formula a(n) = (d(n^2) + 1)/2, as noted in the first comment.

There is a simple construction not mentioned there that nicely demonstrates
the formula: 1/n = 1/(n+a) + 1/(n+b) implies ab = n^2.

The same construction extends to the general case: to write m/n as a sum
of 2 unit fractions, find a factorisation n^2 = xy, such that
n + x == n + y == 0 (mod m). Then m/n = m/(n+x) + m/(n+y), and the RHS

When m = 2, it remains simple: for odd n, any pair of factors of n^2 will
both be odd, so n+x, n+y will be even in every case. So given:

b(n) = Number of ways to write 2/n as a sum of exactly 2 unit fractions
we get:
b(n) = { A018892(n/2)  if n == 0 (mod 2)

For c(n) = Number of ways to write 3/n as a sum of exactly 2 unit fractions,
we need to find the number of ways to split n^2 into 2 factors each
equivalent either to 1 (mod 3) when n == 2 (mod 3), or vice versa.

Writing n = PQ, such that P is a product of primes == 1 (mod 3) and
Q a product of primes == 2 (mod 3), I find:

c(n) = { A018892(n/3)               if n == 0 (mod 3)

I have an approach to prove this, by induction on multiplication of prime
powers, but I suspect it is overly complex: can anyone suggest a simple
proof of c(n)?

I think the 2/n and 3/n cases are interesting enough to submit once I've
for other m, I don't expect to submit those unless they prove unexpectedly
interesting.

Hugo