%I #40 Mar 26 2021 08:44:25

%S 1,2,3,5,6,9,11,14,16,21,23,29,32,36,40,48,51,60,64,70,75,86,90,100,

%T 106,115,121,135,139,154,162,172,180,192,198,216,225,237,245,265,271,

%U 292,302,314,325,348,356,377,387,403,415,441,450,470,482

%N a(n) = A002088(n)/2.

%C a(n) = |{(x,y) : 1 <= x <= y <= n, x + y <= n, 1 = gcd(x,y)}| = |{(x,y) : 1 <= x <= y <= n, x + y > n, 1 = gcd(x,y)}|. - _Steve Butler_, Mar 31 2006

%C Brousseau proved that if the starting numbers of a generalized Fibonacci sequence are <= n (for n > 1) then the number of such sequences with relatively prime successive terms is a(n). - _Amiram Eldar_, Mar 31 2017

%H Giovanni Resta, <a href="/A046657/b046657.txt">Table of n, a(n) for n = 2..10000</a>

%H Alfred Brousseau, <a href="http://www.fq.math.ca/Scanned/10-6/brousseau2.pdf">A Note on the Number of Fibonacci Sequences</a>, The Fibonacci Quarterly, Vol. 10, No. 6 (1972), pp. 657-658.

%F a(n) = 1/2 + Sum_{i<j<=n, gcd(i, j) = 1} i/j. - _Joseph Wheat_, Feb 22 2018

%p a:=n->sum(numtheory[phi](k),k=1..n): seq(a(n)/2, n=2..60); # _Muniru A Asiru_, Mar 05 2018

%t Rest@ Accumulate[EulerPhi@ Range@ 56]/2 (* _Michael De Vlieger_, Apr 02 2017 *)

%o (PARI) a(n) = sum(k=1, n, eulerphi(k))/2; \\ _Michel Marcus_, Apr 01 2017

%o (GAP) List([2..60],n->Sum([1..n],k->Phi(k)/2)); # _Muniru A Asiru_, Mar 05 2018

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def A046657(n): # based on second formula in A018805

%o if n == 0:

%o return 0

%o c, j = 0, 2

%o k1 = n//j

%o while k1 > 1:

%o j2 = n//k1 + 1

%o c += (j2-j)*(4*A046657(k1)-1)

%o j, k1 = j2, n//j2

%o return (n*(n-1)-c+j)//4 # _Chai Wah Wu_, Mar 25 2021

%Y Cf. A002088.

%Y Partial sums of A023022.

%K nonn

%O 2,2

%A _N. J. A. Sloane_