A295515 -id:A295515 - cp's OEIS frontend

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

N. J. A. Sloane, Jun 19 2002

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.

			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, ...

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

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.

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

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 *)

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

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

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)

More terms from Reiner Martin, Jul 08 2002

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

A295511 The Schinzel-Sierpiński tree of fractions, read across levels.

Original entry on oeis.org

2, 2, 2, 3, 3, 2, 3, 7, 7, 5, 5, 7, 7, 3, 2, 5, 17, 13, 7, 11, 11, 5, 5, 11, 11, 7, 13, 17, 5, 2, 3, 11, 241, 193, 17, 29, 29, 13, 7, 17, 17, 11, 31, 43, 43, 13, 13, 43, 43, 31, 11, 17, 17, 7, 13, 29, 29, 17, 193, 241, 11, 3

Offset: 1

Peter Luschny, Nov 23 2017

A conjecture of Schinzel and Sierpiński asserts that every positive rational number r can be represented as a quotient of shifted primes such that r = (p-1)/(q-1).
The function r -> [p, q] will be called the Schinzel-Sierpiński encoding of r if q is the smallest prime such that r = (p-1)/(q-1) for some prime p. In the case that no pair of such primes exists we set by convention p = q = 1.
The Schinzel-Sierpiński tree of fractions is the Euclid tree A295515 with root 1 and fractions represented by the Schinzel-Sierpiński encoding.

			The tree starts:
                                        2/2
                   2/3                                     3/2
         3/7                  7/5                 5/7                   7/3
   2/5       17/13     7/11        11/5     5/11       11/7     13/17        5/2
.
The numerators of the terms written as an array (the denominators are given by reversion of the arrays):
1: 2
2: 2, 3
3: 3, 7, 5, 7
4: 2, 17, 7, 11, 5, 11, 13, 5
5: 3, 241, 17, 29, 7, 17, 31, 43, 13, 43, 11, 17, 13, 29, 193, 11

E. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232.

N. Calkin and H. S. Wilf, Recounting the rationals, Amer. Math. Monthly, 107 (No. 4, 2000), pp. 360-363.
Matthew M. Conroy, A sequence related to a conjecture of Schinzel, J. Integ. Seqs. Vol. 4 (2001), #01.1.7.
P. D. T. A. Elliott, The multiplicative group of rationals generated by the shifted primes. I., J. Reine Angew. Math. 463 (1995), 169-216.
P. D. T. A. Elliott, The multiplicative group of rationals generated by the shifted primes. II. J. Reine Angew. Math. 519 (2000), 59-71.
Peter Luschny, The Schinzel-Sierpiński conjecture and the Calkin-Wilf tree.
A. Malter, D. Schleicher, D. Zagier, New looks at old number theory, Amer. Math. Monthly, 120 (2013), 243-264.
A. Schinzel and W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers, Acta Arithmetica 4 (1958), 185-208; erratum 5 (1958) p. 259.

Cf. A002487, A294442, A295510, A295512, A295515.

def EuclidTree(n): # with root 1
    def DijkstraFusc(m):
        a, b, k = 1, 0, m
        while k > 0:
            if k % 2 == 1: b += a
            else: a += b
            k = k >> 1
        return b
    DF = [DijkstraFusc(k) for k in (2^(n-1)..2^n)]
    return [DF[j]/DF[j+1] for j in (0..2^(n-1)-1)]
def SchinzelSierpinski(l):
    a, b = l.numerator(), l.denominator()
    p, q = 1, 2
    while q < 1000000000: # search limit
        r = a*(q - 1)
        if b.divides(r):
            p = r // b + 1
            if is_prime(p): return p/q
        q = next_prime(q)
    print("Search limit reached for ", l); return 0
def SSETree(level):
    return [SchinzelSierpinski(l) for l in EuclidTree(level)]
# With the imperfection that Sage reduces 2/2 automatically to 1.
for level in (1..6): print(SSETree(level))

A295512 The Euclid tree with root 1 encoded by semiprimes, read across levels.

Original entry on oeis.org

4, -6, 6, -21, 35, -35, 21, -10, 221, -77, 55, -55, 77, -221, 10, -33, 46513, -493, 377, -119, 187, -1333, 559, -559, 1333, -187, 119, -377, 493, -46513, 33, -14, 143, -209, 629, -14527, 2881, -1189, 533, -161, 391, -15229, 2449, -2263, 3139, -1073, 95, -95

Offset: 1

Peter Luschny, Nov 23 2017

The Euclid tree with root 1 is A295515 (sometimes called Calkin-Wilf tree).
For a positive rational r we use the Schinzel-Sierpiński encoding r -> [p, q] as described in A295511 and encode r as sgn*p*q where sgn is -1 if r < 1, else +1.
Apart from a(1) all terms are squarefree.

			The tree starts:
                     4
            -6                 6
       -21       35      -35       21
    -10  221  -77  55  -55  77  -221  10

E. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232.

N. Calkin and H. S. Wilf, Recounting the rationals, Amer. Math. Monthly, 107 (No. 4, 2000), pp. 360-363.
Matthew M. Conroy, A sequence related to a conjecture of Schinzel, J. Integ. Seqs. Vol. 4 (2001), #01.1.7.
P. D. T. A. Elliott, The multiplicative group of rationals generated by the shifted primes. I., J. Reine Angew. Math. 463 (1995), 169-216.
P. D. T. A. Elliott, The multiplicative group of rationals generated by the shifted primes. II. J. Reine Angew. Math. 519 (2000), 59-71.
Peter Luschny, The Schinzel-Sierpiński conjecture and the Calkin-Wilf tree.
A. Malter, D. Schleicher, D. Zagier, New looks at old number theory, Amer. Math. Monthly, 120(3), 2013, pp. 243-264.
A. Schinzel and W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers, Acta Arithmetica 4 (1958), 185-208; erratum 5 (1958) p. 259.

Cf. A294442, A295511, A295515.

EuclidTree := proc(n) local k, DijkstraFusc;
DijkstraFusc := proc(m) option remember; local a, b, n; a := 1; b := 0; n := m;
while n > 0 do if type(n, odd) then b := a+b else a := a+b fi; n := iquo(n,2) od; b end:
seq(DijkstraFusc(k)/DijkstraFusc(k+1), k=2^(n-1)..2^n-1) end:
SchinzelSierpinski := proc(l) local a, b, r, p, q, sgn;
a := numer(l); b := denom(l); q := 2; sgn := `if`(a < b, -1, 1);
while q < 1000000000 do r := a*(q - 1); if r mod b = 0 then p := r/b + 1;
if isprime(p) then return(sgn*p*q) fi fi; q := nextprime(q); od;
print("Search limit reached!", a, b) end:
Tree := level -> seq(SchinzelSierpinski(l), l=EuclidTree(level)): seq(Tree(n), n=1..6);

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

Extensions

A295511 The Schinzel-Sierpiński tree of fractions, read across levels.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Sage

A295512 The Euclid tree with root 1 encoded by semiprimes, read across levels.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple