login
Ljungstrand's sequence: number of distinct solutions to n = (X + 1/x)(Y + 1/y), where x,y > 1 and X,Y are integers.
1

%I #27 Mar 09 2019 00:45:22

%S 0,1,2,3,4,5,5,6,8,8,8,9,8,10,14,12,10,11,10,14,17,14,13,16,18,13,17,

%T 21,13,19,12,14,23,16,26,26,14,17,21,26,16,23,16,22,30,22,18,22,24,22,

%U 26,23,18,28,33,32,29,21,20,32,19,19,30,30,35,27,18,28,31,41,20,33,19

%N Ljungstrand's sequence: number of distinct solutions to n = (X + 1/x)(Y + 1/y), where x,y > 1 and X,Y are integers.

%C a(n) < n and lim_{n->inf} (Sum_{k=1..n} a(k)) / (n*log(n)^3) = 3/(2*Pi^2) (see article).

%H David A. Corneth, <a href="/A086886/b086886.txt">Table of n, a(n) for n = 1..10000</a>

%H J. Brzezinski, W. Holsztynski and P. Kurlberg, <a href="https://arxiv.org/abs/math/0308194">On the congruence ax+by=1 modulo xy</a>, arXiv:math/0308194 [math.NT], 2003.

%H David A. Corneth, <a href="/A086886/a086886.gp.txt">List of distinct solutions for a(n) where n = 1..300</a>

%e 10 = (1+1/19)(9+1/2) = (3+1/13)(3+1/4) = (1+1/14)(9+1/3) = (3+1/8)(3+1/5) = (1+1/11)(9+1/6) = (1+1/5)(8+1/3) = (1+1/3)(7+1/2) = (1+1/10)(9+1/11). These are all 8 distinct such expressions for 10 so a(10) = 8. - _David A. Corneth_, Feb 18 2019

%t w[n_] := Module[{ant = 0}, Do[For[X = 1, X <= Floor[Sqrt[n]], X++, Do[If[ GCD[n-k, X] != X || GCD[n/a + (n-k)/X, k] != k, Continue[]]; Y = (n-k)/X; x = (n/a + (n-k)/X)/k; y = (a+X)/k; If[x == 1 || y == 1, Continue[]]; If[ X == Y, ant = ant+1/2, ant = ant+1], {k, Divisors[a+X]}]], {a, Divisors[n] }]; ant]; Array[w, 73] (* _Jean-François Alcover_, Feb 18 2019, translated from PARI *)

%o (PARI) a(n)=ant=0; fordiv(n, d, for(X=1, floor(sqrt(n)), fordiv(d+X, k, if(gcd(n-k, X)!=X||gcd(n/d+(n-k)/X, k)!=k, next); Y=(n-k)/X; x=(n/d+(n-k)/X)/k; y=(d+X)/k; if(x==1||y==1, next); if(X==Y, ant=ant+1/2, ant=ant+1)))); ant \\ Juliusz Brzezinski

%K nonn

%O 1,3

%A _Ralf Stephan_, Aug 22 2003; revised Dec 08 2004