|
%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_
|
