A071974 Numerator of rational number i/j such that Sagher map sends i/j to n.

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

Offset: 1

Author

N. J. A. Sloane, Jun 19 2002

Keywords

• nonn
• frac
• easy
• nice
• mult

Comments

The Sagher map sends Product p_i^e_i / Product q_i^f_i (p_i and q_i being distinct primes) to Product p_i^(2e_i) * Product q_i^(2f_i-1). This is multiplicative.

Examples

			The Sagher map sends the following fractions to 1, 2, 3, 4, ...: 1/1, 1/2, 1/3, 2/1, 1/5, 1/6, 1/7, 1/4, 3/1, ...
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• David M. Bradley, Counting the Positive Rationals: A Brief Survey, arXiv:math/0509025 [math.HO], 2005.
• Gerald Freilich, A denumerability formula for the rationals, Amer. Math. Monthly, Nov 1965, pp. 1013-1014.
• Kevin McCrimmon, Enumeration of the positive rationals, Amer. Math. Monthly, Nov 1960, p. 868.
• Vaclav Kotesovec, Graph - the asymptotic ratio (10000 terms)
• Yoram Sagher, Counting the rationals, Amer. Math. Monthly, 96 (1989), p. 823. Math. Rev. 90i:04001.
• Index entries for sequences related to enumerating the rationals

Crossrefs

Cf. A071975. Differs from A056622 at a(32).

Cf. A000290, A027748, A077591, A124010, A350388.

For other bijective mappings from integers to positive rationals see A002487, A020652/A020653, A038568/A038569, A229994/A077610, A295515.

Cf. A307868.

Programs

Haskell

a071974 n = product $ zipWith (^) (a027748_row n) $
   map (\e -> (1 - e `mod` 2) * e `div` 2) $ a124010_row n
-- Reinhard Zumkeller, Jun 15 2012

Mathematica

f[{p_, a_}] := If[EvenQ[a], p^(a/2), 1]; a[n_] := Times@@(f/@FactorInteger[n])
Table[Sqrt@ SelectFirst[Reverse@ Divisors@ n, And[IntegerQ@ Sqrt@ #, CoprimeQ[#, n/#]] &], {n, 104}] (* Michael De Vlieger, Dec 06 2018 *)

PARI

a(n)=local(v=factor(n)~); prod(k=1,length(v),if(v[2,k]%2,1,v[1,k]^(v[2,k]/2)))

Python

from math import prod
from sympy import factorint
def A071974(n): return prod(p**(e>>1) for p, e in factorint(n).items() if e&1^1) # Chai Wah Wu, Jul 27 2024

Formula

If n=Product p_i^e_i, then a_n=Product p_i^f(e_i), where f(n)=n/2 if n is even and f(n)=0 if n is odd. - Reiner Martin, Jul 08 2002

a(n^2) = n, A071975(n^2) = 1, cf. A000290; a(2*(2*n-1)^2) = 2*n+1, A071975(2*(2*n-1)^2) = 2, cf. A077591. - Reinhard Zumkeller, Jul 10 2011

From Amiram Eldar, Nov 02 2023, Jul 26 2024: (Start)

a(n) = sqrt(A350388(n)) (square root of largest unitary divisor of n that is a square).

Dirichlet g.f.: zeta(2*s) * zeta(2*s-1) * Product_{p prime} (1 + 1/p^s - 1/p^(2*s) - 1/p^(3*s-1)). (End)

From Vaclav Kotesovec, May 05 2025: (Start)

Let f(s) = Product_{p prime} (1 - (p^s + p)/((p^s + 1)*p^(2*s))).

Dirichlet g.f.: zeta(s) * zeta(2*s-1) * f(s).

Sum_{k=1..n} a(k) ~ f(1) * n * (log(n) + 3*gamma - 1 + f'(1)/f(1)) / 2, where

f(1) = A307868 = Product_{p prime} (1 - 2/(p*(1+p))) = 0.4716806136129978680752356330804820874259263820069868836357372554177321...

f'(1) = f(1) * Sum_{p prime} (5*p+3)*log(p) / ((p+1)*(p^2+p-2)) = f(1) * 2.1244279471327068377850377690765768532203174482128717024402373817115555...

and gamma is the Euler-Mascheroni constant A001620. (End)

Extensions

More terms from Reiner Martin, Jul 08 2002

Additional references supplied by Kevin Ryde added by N. J. A. Sloane, May 31 2012