A245718 -id:A245718 - cp's OEIS frontend

A023022 Number of partitions of n into two relatively prime parts. After initial term, this is the "half-totient" function phi(n)/2 (A000010(n)/2).

1, 1, 1, 2, 1, 3, 2, 3, 2, 5, 2, 6, 3, 4, 4, 8, 3, 9, 4, 6, 5, 11, 4, 10, 6, 9, 6, 14, 4, 15, 8, 10, 8, 12, 6, 18, 9, 12, 8, 20, 6, 21, 10, 12, 11, 23, 8, 21, 10, 16, 12, 26, 9, 20, 12, 18, 14, 29, 8, 30, 15, 18, 16, 24, 10, 33, 16, 22, 12, 35, 12, 36, 18, 20, 18, 30, 12, 39, 16, 27, 20, 41, 12

Offset: 2

N. J. A. Sloane

The number of distinct linear fractional transformations of order n. Also the half-totient function can be used to construct a tree containing all the integers. On the zeroth rank we have just the integers 1 and 2: immediate "ancestors" of 1 and 2 are (1: 3,4,6 2: 5,8,10,12) etc. - Benoit Cloitre, Jun 03 2002
Moebius transform of floor(n/2). - Paul Barry, Mar 20 2005
Also number of different kinds of regular n-gons, one convex, the others self-intersecting. - Reinhard Zumkeller, Aug 20 2005
From Artur Jasinski, Oct 28 2008: (Start)
Degrees of minimal polynomials of cos(2*Pi/n). The first few are
   1: x - 1
   2: x + 1
   3: 2*x + 1
   4: x
   5: 4*x^2 + 2*x - 1
   6: 2*x - 1
   7: 8*x^3 + 4*x^2 - 4*x - 1
   8: 2*x^2 - 1
   9: 8*x^3 - 6*x + 1
  10: 4*x^2 - 2*x - 1
  11: 32*x^5 + 16*x^4 - 32*x^3 - 12*x^2 + 6*x + 1
These polynomials have solvable Galois groups, so their roots can be expressed by radicals. (End)
a(n) is the number of rationals p/q in the interval [0,1] such that p + q = n. - Geoffrey Critzer, Oct 10 2011
It appears that, for n > 2, a(n) = A023896(n)/n. Also, it appears that a record occurs at n > 2 in this sequence if and only if n is a prime.  For example, records occur at n=5, 7, 11, 13, 17, ..., all of which are prime. - John W. Layman, Mar 26 2012
From Wolfdieter Lang, Dec 19 2013: (Start)
a(n) is the degree of the algebraic number of s(n)^2 = (2*sin(Pi/n))^2, starting at a(1)=1. s(n) = 2*sin(Pi/n) is the length ratio side/R for a regular n-gon inscribed in a circle of radius R (in some length units). For the coefficient table of the minimal polynomials of s(n)^2 see A232633.
Because for even n, s(n)^2 lives in the algebraic number field Q(rho(n/2)), with rho(k) = 2*cos(Pi/k), the degree is a(2*l) = A055034(l). For odd n, s(n)^2 is an integer in Q(rho(n)), and the degree is a(2*l+1) = A055034(2*l+1) = phi(2*l+1)/2, l >= 1, with Euler's totient phi=A000010 and a(1)=1. See also A232631-A232633.
(End)
Also for n > 2: number of fractions A182972(k)/A182973(k) such that A182972(k) + A182973(k) = n, A182972(n) and A182973(n) provide an enumeration of positive rationals < 1 arranged by increasing sum of numerator and denominator then by increasing numerator. - Reinhard Zumkeller, Jul 30 2014
Number of distinct rectangles with relatively prime length and width such that L + W = n, W <= L. For a(17)=8; the rectangles are 1 X 16, 2 X 15, 3 X 14, 4 X 13, 5 X 12, 6 X 11, 7 X 10, 8 X 9. - Wesley Ivan Hurt, Nov 12 2017
After including a(1) = 1, the number of elements of any reduced residue system mod* n used by Brändli and Beyne is a(n). See the examples below. - Wolfdieter Lang, Apr 22 2020
a(n) is the number of ABC triples with n = c. - Felix Huber, Oct 12 2023

			a(15)=4 because there are 4 partitions of 15 into two parts that are relatively prime: 14 + 1, 13 + 2, 11 + 4, 8 + 7. - _Geoffrey Critzer_, Jan 25 2015
The smallest nonnegative reduced residue system mod*(n) for n = 1 is {0}, hence a(1) = 1; for n = 9 it is {1, 2, 4}, because 5 == 4 (mod* 9) since -5 == 4 (mod 9), 7 == 2 (mod* 9) and 8 == 1 (mod* 9). Hence a(9) = phi(9)/2 = 3. See the comment on Brändli and Beyne above. - _Wolfdieter Lang_, Apr 22 2020

G. Pólya and G. Szegő, Problems and Theorems in Analysis I (Springer 1924, reprinted 1972), Part Eight, Chap. 1, Sect. 6, Problems 60&61.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 2..10000
Gerold Brändli and Tim Beyne, Modified Congruence Modulo n with Half the Amount of Residues, arXiv:1504.02757 [math.NT], 2016.
K. S. Brown, The Half-Totient Tree
Tianxin Cai, Zhongyan Shen, and Mengjun Hu, On the Parity of the Generalized Euler Function, Advances in Mathematics (China), 2013, 42(4): 505-510.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
Sameen Ahmed Khan, Trigonometric Ratios Using Algebraic Methods, Mathematics and Statistics (2021) Vol. 9, No. 6, 899-907.
Wolfdieter Lang, On the Equivalence of Three Complete Cyclic Systems of Integers, arXiv:2008.04300 [math.NT], 2020.
Jorma K. Merikoski, Pentti Haukkanen, and Timo Tossavainen, The congruence x^n = -a^n (mod m): Solvability and related OEIS sequences, Notes. Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 516-529. See p. 518.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Pinthira Tangsupphathawat, Takao Komatsu, and Vichian Laohakosol, Minimal Polynomials of Algebraic Cosine Values, II, J. Int. Seq., Vol. 21 (2018), Article 18.9.5.
Eric Weisstein's World of Mathematics, Polygon Triangle Picking
Eric Weisstein's World of Mathematics, Trigonometry Angles
Canze Zhu and Qunying Liao, A recursion formula for the generalized Euler function phi_e(n), arXiv:2105.10870 [math.NT], 2021.

Cf. A000010, A055684, A046657, A049806, A049703, A062956.
Cf. A181875, A181876, A181877, A183918.
Cf. A023896.
Cf. A182972, A182973, A245497, A245718.

a023022 n = length [(u, v) | u <- [1 .. div n 2],
                             let v = n - u, gcd u v == 1]
-- Reinhard Zumkeller, Jul 30 2014

[1] cat [EulerPhi(n)/ 2: n in [3..100]]; // Vincenzo Librandi, Aug 19 2018

A023022 := proc(n)
    if n =2 then
        1;
    else
        numtheory[phi](n)/2 ;
    end if;
end proc:
seq(A023022(n),n=2..60) ; # R. J. Mathar, Sep 19 2017

Join[{1}, Table[EulerPhi[n]/2, {n, 3, 100}]] (* adapted by Vincenzo Librandi, Aug 19 2018 *)

a(n)=if(n<=2,1,eulerphi(n)/2);
/* for printing minimal polynomials of cos(2*Pi/n) */
default(realprecision,110);
for(n=1,33,print(n,": ",algdep(cos(2*Pi/n),a(n))));

from sympy.ntheory import totient
def a(n): return 1 if n<3 else totient(n)/2 # Indranil Ghosh, Mar 30 2017

a(n) = phi(n)/2 for n >= 3.
a(n) = (1/n)*Sum_{k=1..n-1, gcd(n, k)=1} k = A023896(n)/n for n>2. - Reinhard Zumkeller, Aug 20 2005
G.f.: x*(x - 1)/2 + (1/2)*Sum_{k>=1} mu(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Apr 13 2017
a(n) = Sum_{d|n} moebius(n/d)*floor(d/2). - Michel Marcus, May 25 2021

This was in the 1973 "Handbook", but then was dropped from the database. Resubmitted by David W. Wilson
Entry revised by N. J. A. Sloane, Jun 10 2012
Polynomials edited with the consent of Artur Jasinski by Wolfdieter Lang, Jan 08 2011
Name clarified by Geoffrey Critzer, Jan 25 2015

A182972 Numerators of positive rationals < 1 arranged by increasing sum of numerator and denominator then by increasing numerator.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 3, 1, 3, 1, 2, 4, 1, 3, 1, 2, 3, 4, 5, 1, 5, 1, 2, 3, 4, 5, 6, 1, 3, 5, 1, 2, 4, 7, 1, 3, 5, 7, 1, 2, 3, 4, 5, 6, 7, 8, 1, 5, 7, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 3, 7, 9, 1, 2, 4, 5, 8, 10, 1, 3, 5, 7, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1, 5, 7, 11, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 1, 3, 5, 7, 9, 11

Offset: 1

William Rex Marshall, Dec 16 2010

A023022(n) and A245677(n) give number and numerator of sum of fractions a(k)/A182973(k) such that a(k) + A182973(k) = n. - Reinhard Zumkeller, Jul 30 2014

			Positive fractions < 1 listed by increasing sum of numerator and denominator, and by increasing numerator for equal sums:
1/2
1/3
1/4 2/3
1/5
1/6 2/5 3/4
1/7 3/5
1/8 2/7 4/5
1/9 3/7
1/10 2/9 3/8 4/7 5/6
1/11 5/7
1/12 2/11 3/10 4/9 5/8 6/7
1/13 3/11 5/9
1/14 2/13 4/11 7/8
1/15 3/13 5/11 7/9
1/16 2/15 3/14 4/13 5/12 6/11 7/10 8/9
1/17 5/13 7/11
1/18 2/17 3/16 4/15 5/14 6/13 7/12 8/11 9/10
1/19 3/17 7/13 9/11
(this is A182972/A182973).

S. Cook, Problem 511: An Enumeration Problem, Journal of Recreational Mathematics, Vol. 9:2 (1976-77), 137. Solution by the Problem Editor, JRM, Vol. 10:2 (1977-78), 122-123.
R. K. Guy, Unsolved Problems in Number Theory (UPINT), Section D11.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Paul Yiu, Recreational Mathematics, 24.3.1 Appendix: Two enumerations of the rational numbers in (0,1), page 633.
Index entries for sequences related to enumerating the rationals

Cf. A182973 (denominators), A366191 (interleaved).
Cf. A020652, A038567, A182974, A182975, A182976.
Cf. A023022, A245677, A245678, A245718.
Essentially the same as A333856.

a182972 n = a182972_list !! (n-1)
a182972_list = map fst $ concatMap q [3..] where
   q x = [(num, den) | num <- [1 .. div x 2],
                       let den = x - num, gcd num den == 1]
-- Reinhard Zumkeller, Jul 29 2014

t1:=[];
for n from 2 to 40 do
t1:=[op(t1),1/(n-1)];
for i from 2 to floor((n-1)/2) do
   if gcd(i,n-i)=1 then t1:=[op(t1),i/(n-i)]; fi; od:
od:
t1;

t1={}; For[n=2, n <= 40, n++, AppendTo[t1, 1/(n-1)]; For[i=2, i <= Floor[(n-1)/2], i++, If[GCD[i, n-i] == 1, AppendTo[t1, i/(n-i)]]]]; t1 // Numerator // Rest (* Jean-François Alcover, Jan 20 2015, translated from Maple *)

program a182972;
var
  num,den,n: longint;
function gcd(i,j: longint):longint;
begin
  repeat
    if i>j then i:=i mod j else j:=j mod i;
  until (i=0) or (j=0);
  if i=0 then gcd:=j else gcd:=i;
end;
begin
  num:=1; den:=1; n:=0;
  repeat
    repeat
      inc(num); dec(den);
      if num>=den then
      begin
        inc(den,num); num:=1;
      end;
    until gcd(num,den)=1;
    inc(n); writeln(n,' ',num);
  until n=100000;
end.

from itertools import count, islice
from math import gcd
def A182972_gen(): # generator of terms
    return (i for n in count(2) for i in range(1,1+(n-1>>1)) if gcd(i,n-i)==1)
A182972_list = list(islice(A182972_gen(),10)) # Chai Wah Wu, Aug 28 2023

Corrected by William Rex Marshall, Aug 12 2013

A182973 Denominators of positive rationals < 1 arranged by increasing sum of numerator and denominator then by increasing numerator.

Original entry on oeis.org

2, 3, 4, 3, 5, 6, 5, 4, 7, 5, 8, 7, 5, 9, 7, 10, 9, 8, 7, 6, 11, 7, 12, 11, 10, 9, 8, 7, 13, 11, 9, 14, 13, 11, 8, 15, 13, 11, 9, 16, 15, 14, 13, 12, 11, 10, 9, 17, 13, 11, 18, 17, 16, 15, 14, 13, 12, 11, 10, 19, 17, 13, 11, 20, 19, 17, 16, 13, 11, 21, 19, 17, 15, 13, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12

Offset: 1

William Rex Marshall, Dec 16 2010

A023022(n) and A245678(n) give number and denominator of sum of fractions A182972(k)/a(k) such that A182972(k) + a(k) = n. - Reinhard Zumkeller, Jul 30 2014

			Positive fractions < 1 listed by increasing sum of numerator and denominator, and by increasing numerator for equal sums:
1/2, 1/3, 1/4, 2/3, 1/5, 1/6, 2/5, 3/4, 1/7, 3/5, 1/8, 2/7, 4/5, 1/9, 3/7, ...
(this is A182972/A182973).

S. Cook, Problem 511: An Enumeration Problem, Journal of Recreational Mathematics, Vol. 9:2 (1976-77), 137. Solution by the Problem Editor, JRM, Vol. 10:2 (1977-78), 122-123.
R. K. Guy, Unsolved Problems in Number Theory (UPINT), Section D11.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Paul Yiu, Recreational Mathematics, 24.3.1 Appendix: Two enumerations of the rational numbers in (0,1), page 633.
Index entries for sequences related to enumerating the rationals

Cf. A182972 (numerators), A366191 (interleaved).
Cf. A020652, A038567, A182974-A182976.
Cf. A023022, A245677, A245678, A245718.

a182973 n = a182973_list !! (n-1)
a182973_list = map snd $ concatMap q [3..] where
   q x = [(num, den) | num <- [1 .. div x 2],
                       let den = x - num, gcd num den == 1]
-- Reinhard Zumkeller, Jul 29 2014

A182973list[s_] := Table[If[CoprimeQ[num, s-num], s-num, Nothing], {num, Floor[s/2]}]; Flatten[Array[A182973list, 25, 3]] (* Paolo Xausa, Feb 27 2024 *)

program a182973;
var
  num,den,n: longint;
function gcd(i,j: longint):longint;
begin
  repeat
    if i>j then i:=i mod j else j:=j mod i;
  until (i=0) or (j=0);
  if i=0 then gcd:=j else gcd:=i;
end;
begin
  num:=1; den:=1; n:=0;
  repeat
    repeat
      inc(num); dec(den);
      if num>=den then
      begin
        inc(den,num); num:=1;
      end;
    until gcd(num,den)=1;
    inc(n); writeln(n,' ',den);
  until n=100000;
end.

from itertools import count, islice
from math import gcd
def A182973_gen(): # generator of terms
    return (n-i for n in count(2) for i in range(1,1+(n-1>>1)) if gcd(i,n-i)==1)
A182973_list = list(islice(A182973_gen(),10)) # Chai Wah Wu, Aug 28 2023

A245677 Numerator of sum of fractions A182972(k) / A182973(k) such that A182972(k) + A182973(k) = n.

Original entry on oeis.org

1, 1, 11, 1, 79, 26, 339, 34, 5297, 62, 69071, 1165, 11723, 9844, 471181, 2625, 8960447, 73244, 8231001, 243757, 1031626241, 151100, 4178462515, 2651758, 10396147563, 11843614, 64166447971, 362476, 1989542332021, 97275764008, 1830230212061, 57286319768

Offset: 3

Reinhard Zumkeller, Jul 30 2014

A182972(n) and A182973(n) provide an enumeration of positive rationals < 1 arranged by increasing sum of numerator and denominator then by increasing numerator;
a(n) = numerator(sum(A182972(k)/A182973(k): k such that A182972(k)+A182973(k)=n));
A245718(n) = floor(a(n)/A245678(n)).

			.     |  (num, den) = (A182973, A182973) | num(sum)| den(sum)|   [sum]
.   n |  num/den,   num + den = n        | A245677 | A245678 | A245718
. ----+----------------------------------+---------+---------+--------
.   3 |  1/2                             |       1 |       2 |       0
.   4 |  1/3                             |       1 |       3 |       0
.   5 |  1/4, 2/3                        |      11 |      12 |       0
.   6 |  1/5                             |       1 |       5 |       0
.   7 |  1/6, 2/5, 3/4                   |      79 |      60 |       1
.   8 |  1/7, 3/5                        |      26 |      35 |       0
.   9 |  1/8, 2/7, 4/5                   |     339 |     280 |       1
.  10 |  1/9, 3/7                        |      34 |      63 |       0
.  11 |  1/10, 2/9, 3/8, 4/7, 5/6        |    5297 |    2520 |       2
.  12 |  1/11, 5/7                       |      62 |      77 |       0
.  13 |  1/12, 2/11, 3/10, 4/9, 5/8, 6/7 |   69071 |   27720 |       2
.  14 |  1/13, 3/11, 5/9                 |    1165 |    1287 |       0
.  15 |  1/14, 2/13, 4/11, 7/8           |   11723 |    8008 |       1
.  16 |  1/15, 3/13, 5/11, 7/9           |    9844 |    6435 |       1 .

Reinhard Zumkeller, Table of n, a(n) for n = 3..1000
Paul Yiu, Recreational Mathematics, 24.3.1 Appendix: Two enumerations of the rational numbers in (0,1), page 633.

Cf. A245678 (denominator), A182972, A182973, A245718.

import Data.Ratio ((%), numerator)
a245677 n = numerator $ sum
   [num % den | num <- [1 .. div n 2], let den = n - num, gcd num den == 1]

cp's OEIS Frontend

A023022 Number of partitions of n into two relatively prime parts. After initial term, this is the "half-totient" function phi(n)/2 (A000010(n)/2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A182972 Numerators of positive rationals < 1 arranged by increasing sum of numerator and denominator then by increasing numerator.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Pascal

Python

Extensions

A182973 Denominators of positive rationals < 1 arranged by increasing sum of numerator and denominator then by increasing numerator.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Pascal

Python

A245677 Numerator of sum of fractions A182972(k) / A182973(k) such that A182972(k) + A182973(k) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

A245678 Denominator of sum of fractions A182972(k) / A182973(k) such that A182972(k) + A182973(k) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell