cp's OEIS Frontend

A046657 a(n) = A002088(n)/2.

%I A046657 #42 Jan 05 2025 19:51:35
%S A046657 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 A046657 106,115,121,135,139,154,162,172,180,192,198,216,225,237,245,265,271,
%U A046657 292,302,314,325,348,356,377,387,403,415,441,450,470,482
%N A046657 a(n) = A002088(n)/2.
%C A046657 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 A046657 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 A046657 Giovanni Resta, <a href="/A046657/b046657.txt">Table of n, a(n) for n = 2..10000</a>
%H A046657 Alfred Brousseau, <a href="https://web.archive.org/web/2024*/https://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 A046657 a(n) = 1/2 + Sum_{i<j<=n, gcd(i, j) = 1} i/j. - _Joseph Wheat_, Feb 22 2018
%p A046657 a:=n->sum(numtheory[phi](k),k=1..n): seq(a(n)/2, n=2..60); # _Muniru A Asiru_, Mar 05 2018
%t A046657 Rest@ Accumulate[EulerPhi@ Range@ 56]/2 (* _Michael De Vlieger_, Apr 02 2017 *)
%o A046657 (PARI) a(n) = sum(k=1, n, eulerphi(k))/2; \\ _Michel Marcus_, Apr 01 2017
%o A046657 (GAP) List([2..60],n->Sum([1..n],k->Phi(k)/2)); # _Muniru A Asiru_, Mar 05 2018
%o A046657 (Python)
%o A046657 from functools import lru_cache
%o A046657 @lru_cache(maxsize=None)
%o A046657 def A046657(n): # based on second formula in A018805
%o A046657     if n == 0:
%o A046657         return 0
%o A046657     c, j = 0, 2
%o A046657     k1 = n//j
%o A046657     while k1 > 1:
%o A046657         j2 = n//k1 + 1
%o A046657         c += (j2-j)*(4*A046657(k1)-1)
%o A046657         j, k1 = j2, n//j2
%o A046657     return (n*(n-1)-c+j)//4 # _Chai Wah Wu_, Mar 25 2021
%Y A046657 Cf. A002088.
%Y A046657 Partial sums of A023022.
%K A046657 nonn
%O A046657 2,2
%A A046657 _N. J. A. Sloane_