A368457 -id:A368457 - cp's OEIS frontend

A368207 Bacher numbers: number of nonnegative representations of n = wx+yz with max(w,x) < min(y,z).

1, 2, 2, 5, 3, 8, 4, 8, 9, 9, 6, 18, 7, 12, 14, 19, 9, 20, 10, 27, 16, 18, 12, 34, 20, 21, 20, 30, 15, 44, 16, 32, 24, 27, 30, 51, 19, 30, 28, 49, 21, 58, 22, 42, 41, 36, 24, 70, 35, 47, 36, 49, 27, 66, 36, 72, 40, 45, 30, 88, 31, 48, 62, 71, 42, 74, 34, 63, 48

Offset: 1

Don Knuth, Dec 16 2023

nonn

When n = p is an odd prime, Bacher proved that a(p) = (p+1)/2.
It appears that also a(k*p) = sigma(k)*(p+1)/2, for all prime p > 2k, where sigma(k) is the sum of the divisors of k (A000203).
It appears furthermore that a(p^2) = (p^2 + 3*p)/2; a(p^3) = (p^3 + p^2 + p + 1)/2; a(p^4) = (p^4 + p^3 + 3p^2 + p)/2, for all prime p.
Conjectures: (1) a(n) >= sigma(n)/2, with equality if and only if n has no middle divisors, i.e., if and only if n is in A071561. (2) a(n)/sigma(n) converges to 1/2. - Pontus von Brömssen, Dec 18 2023
From Chai Wah Wu, Dec 19 2023: (Start)
Considering representations where min(w,x)=0 shows that a(n) >= 2*A066839(n) - A038548(n).
It appears that a(p^5) = (p^5 + p^4 + p^3 + p^2 + p + 1)/2 for all prime p > 2 and a(p^6) = (p^6 + p^5 + p^4 + 3p^3 + p^2 + p)/2 for all prime p.
Conjecture: a(p^m) = sigma(p^m)/2 for odd m and all prime p > 2. a(p^m) = (sigma(p^m)-1)/2 + p^(m/2) for even m and all prime p. a(2^m) = sigma(2^m)/2 + 1/2 for m odd. (End)

			For n = 13, the a(13) = 7 solutions are (w,x,y,z) = (0,0,1,13), (0,0,13,1), (1,1,2,6), (1,1,3,4), (1,1,4,3), (1,1,6,2), (2,2,3,3).

Don Knuth, Table of n, a(n) for n = 1..10000
Roland Bacher, A quixotic proof of Fermat's two squares theorem for prime numbers, American Mathematical Monthly, Vol. 130, No. 9 (November 2023), 824-836; arXiv version, arXiv:2210.07657 [math.NT], 2022.
Michael S. Branicky, Python translation of Knuth's CWEB program
Pontus von Brömssen, Plot of (n, a(n) - sigma(n)/2) for n = 1..100000.
Pontus von Brömssen, Plot of (n, b(n)) for n = 1..100000, where a(n) = sigma(n)/2 + b(n)*sqrt(n).
Don Knuth, CWEB program.
Peter Luschny, A Formula for the Bacher Numbers.

Cf. A000203, A071561, A368276 (monotone), A368341 (fixed points), A368457, A368458 (semiprimes), A368580 (degenerated).

CWEB
```
@ See Knuth link.
```

function A368207(n)
    t(n) = (d for d in divisors(n) if d * d <= n)
    s(d) = d * d == n ? d * 2 - 1 : d * 4 - 2
    c(y, w, wx) = max(1, 2*(Int(w*w < wx) + Int(y*y < n - wx)))
    sum(sum(sum(c(y, w, wx) for y in t(n - wx) if wx < y * w; init=0)
    for w in t(wx)) for wx in 1:div(n, 2); init=sum(s(d) for d in t(n)))
end
println([A368207(n) for n in 1:69])  # Peter Luschny, Dec 21 2023

t[n_] := t[n] = Select[Divisors[n], #^2 <= n&];
A368207[n_] := Sum[(1 + Boole[d^2 < n])(2d - 1),{d, t[n]}] + Sum[If[wx < y*w, Max[1, 2(Boole[w^2 < wx] + Boole[y^2 < n-wx])], 0], {wx, Floor[n/2]},{w, t[wx]}, {y, t[n - wx]}];
Array[A368207, 100] (* Paolo Xausa, Jan 02 2024 *)

# See Branicky link for translation of Knuth's CWEB program.

from math import isqrt
def A368207(n):
    c, r = 0, isqrt(n)
    for w in range(r+1):
        for x in range(w,r+1):
            wx = w*x
            if wx>n:
                break
            for y in range(x+1,r+1):
                for z in range(y,n+1):
                    yz = wx+y*z
                    if yz>n:
                        break
                    if yz==n:
                        m = 1
                        if w!=x:
                            m<<=1
                        if y!=z:
                            m<<=1
                        c+=m
    return c # Chai Wah Wu, Dec 19 2023

from sympy import divisors
# faster program
def A368207(n):
    c = 0
    for d2 in divisors(n):
        if d2**2 > n:
            break
        c += (d2<<2)-2 if d2**2>1)+1):
        for d1 in divisors(wx):
            if d1**2 > wx:
                break
            for d2 in divisors(m:=n-wx):
                if d2**2 > m:
                    break
                if wx < d1*d2:
                    k = 1
                    if d1**2 != wx:
                        k <<=1
                    if d2**2 != m:
                        k <<=1
                    c+=k
    return c # Chai Wah Wu, Dec 19 2023

Let t(n) = {d|n and d*d <= n}, and s(d, n) = 2*d - 1 if d*d = n, otherwise 4*d - 2. Then a(n) = (Sum_{d in t(n)} s(d, n)) + (Sum_{k=1..floor(n/2)} Sum_{w in t(k)} Sum_{y in t(n-k) and k < y*w} max(1, 2*([w*w < k] + [y*y < n - k]))), where [] denote the Iverson brackets. (See the 'Julia' implementation below.) - Peter Luschny, Dec 21 2023

A368276 Number of nonnegative representations of n = wx + yz with max(w, x) < min(y, z) and w <= x <= y <= z.

Original entry on oeis.org

1, 1, 1, 3, 2, 3, 2, 3, 5, 4, 3, 6, 4, 4, 5, 9, 4, 7, 5, 9, 6, 7, 4, 11, 11, 7, 7, 11, 7, 13, 7, 10, 9, 10, 9, 19, 9, 9, 10, 17, 9, 17, 8, 14, 14, 13, 7, 21, 17, 14, 13, 17, 10, 20, 13, 22, 14, 15, 10, 26, 14, 13, 18, 28, 15, 22, 13, 19, 17, 25, 12, 33, 15, 18

Offset: 1

Peter Luschny, Dec 19 2023

nonn

Number of monotone Bacher representations (A368207) of n. We call a quadruple (w, x, y, z) of nonnegative integers a monotone Bacher representation of n if and only if n = w*x + y*z and w <= x < y <= z.

			For n = 13, the 4 solutions are (w, x, y, z) = (0, 0, 1, 13), (1, 1, 2, 6), (1, 1, 3, 4), (2, 2, 3, 3).

Roland Bacher, A quixotic proof of Fermat's two squares theorem for prime numbers, American Mathematical Monthly, Vol. 130, No. 9 (November 2023), 824-836; arXiv version, arXiv:2210.07657 [math.NT], 2023.

Cf. A368207, A368276, A368457, A368458, A368459, A368580, A368581.

using Nemo
function A368276(n)
    t(n) = (d for d in divisors(n) if d * d <= n)
    sum(sum(sum(1 for d in t(n - wx) if wx < d * dx; init=0)
            for dx in t(wx)) for wx in 1:div(n, 2); init=sum(t(n)))
end
println([A368276(n) for n in 1:74])  # Peter Luschny, Dec 19 2023

t[n_]:=t[n]=Select[Divisors[n],#^2<=n&];
A368276[n_]:=Total[t[n]]+Sum[Boole[wxA368276,100] (* Paolo Xausa, Jan 02 2024 *)

from itertools import takewhile
from sympy import divisors
def A368276(n):
    c = sum(takewhile(lambda x: x**2 <= n, divisors(n)))
    for wx in range(1, (n >> 1) + 1):
        for d1 in divisors(wx):
            if d1**2 > wx:
                break
            m = n - wx
            c += sum(1
                for d in takewhile(lambda x: x**2 <= m, divisors(n - wx))
                if wx < d * d1)
    return c  # Chai Wah Wu, Dec 19 2023

A368458 Numbers k such that 2*(Bacher(k) - sigma(k)) + k + 1 > 0.

Original entry on oeis.org

1, 2, 4, 9, 25, 49, 121, 143, 169, 221, 289, 323, 361, 391, 437, 529, 667, 713, 841, 899, 961, 1073, 1147, 1271, 1333, 1369, 1517, 1591, 1681, 1739, 1763, 1849, 1927, 2021, 2173, 2209, 2279, 2491, 2537, 2773, 2809, 2867, 3127, 3233, 3481, 3551, 3599, 3721, 3763

Offset: 1

Peter Luschny, Dec 26 2023

nonn

We can use the Bacher numbers A368207 to measure the primeness of a positive integer, similar to how the number of prime factors of an integer does, but based on the number of representations of n as w*x + y*z with max(w, x) < min(y, z). Taking b(n) = 2*(Bacher(n) - sigma(n)) + n + 1 as the measure, Bacher's theorem shows that b(n) = 0 if n is an odd prime. Conversely, if b(n) = 0, we cannot conclude that n is prime as the example n = 35 shows, but this is probably the only exception.
This sequence gives the integers k for which b(k) is positive, and A368459 provides those for which b(k) is negative.
Apart from the first three terms, all terms are apparently odd semiprimes (A046315); they are odd composite numbers that cannot be divided by smaller composite numbers.

			To zoom into the internal order of the terms, the sequence can also be written as an irregular triangle (for n >= 3). It starts:
      4;
      9;
     25;
     49;
    121,  143;
    169,  221;
    289,  323;
    361,  391, 437;
    529,  667, 713;
    841,  899;
    961, 1073, 1147, 1271, 1333;
   1369, 1517, 1591;
   1681, 1739, 1763,
   1849, 1927, 2021, 2173;
A row contains the terms between consecutive squares of primes, p^2 included and p'^2 excluded. The first column is the squares of primes A001248. The length of the rows is A368460.

Peter Luschny, Table of n, a(n) for n = 1..1000
Roland Bacher, A quixotic proof of Fermat's two squares theorem for prime numbers, American Mathematical Monthly, Vol. 130, No. 9 (November 2023), 824-836; arXiv version, arXiv:2210.07657 [math.NT], 2022.

Cf. A000203, A046315, A001248, A368207, A368457, A368459, A368460.

using Nemo
function A368458List(slicenum::Int)
    results = [Int[] for _ in 1:slicenum + 1]
    slicelen = 1000
    Threads.@threads for sl in 1:slicenum
        first = (sl - 1) * slicelen + 1
        last = first + slicelen - 1
        result = results[sl]
        for n in first:2:last
            rem(n, 5) == 0 && continue
            if 2 * (divisor_sigma(n, 1) - A368207(n)) < n + 1
                push!(result, n)
    end end end
    results[slicenum + 1] = [2, 4, 25]
    sort(reduce(vcat, results))
end
print(A368458List(5)) # returns values up to param * 1000

from itertools import islice
def A368207(n):
    def t(n): return (d for d in divisors(n) if d*d <= n)
    def s(d): return 2*d - 1 if d*d == n else 4*d - 2
    def c(y, w, wx): return max(1, 2*((w*w < wx) + (y*y < n - wx)))
    return sum((sum(sum((c(y, w, wx) for y in t(n-wx) if wx < y*w), start=0)
    for w in t(wx)) for wx in range(1, n//2)),
    start=sum(s(d) for d in t(n)))
def A368457(n): return 2 * (A368207(n) - sigma(n)) + n + 1
def isA368458(n): return 0 < A368457(n)
def A368458Gen(n):
    while True:
        if isA368458(n): yield n
        n += 1
def A368458List(start, size): return list(islice(A368458Gen(start), size))
print(A368458List(1, 20))

k is a term <=> A368457(k) > 0 <=> 2*(A368207(k) - A000203(k)) + k + 1 > 0.

A368459 Numbers k such that 2*(Bacher(k) - sigma(k)) + k + 1 < 0.

Original entry on oeis.org

6, 8, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30, 32, 33, 34, 36, 38, 39, 40, 42, 44, 45, 46, 48, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95

Offset: 1

Peter Luschny, Dec 26 2023

nonn

Complementary to A368458, this sequence lists the indices of negative values of A368457. See the comments in A368458.

In summary, A368458 U A368459 U Primes U {35, ...} decomposes the positive integers into disjoint sets, whereby the nature of the fourth set is currently unclear; probably, it has only 35 as a member.

Roland Bacher, A quixotic proof of Fermat's two squares theorem for prime numbers, American Mathematical Monthly, Vol. 130, No. 9 (November 2023), 824-836; arXiv version, arXiv:2210.07657 [math.NT], 2022.

Cf. A000203, A100484, A001248, A368207, A368457, A368458, A368460.

println([n for n in 1:95 if A368457(n) < 0])

k is a term <=> A368457(k) < 0 <=> 2*(A368207(k) - A000203(k)) + k + 1 < 0.

A368460 a(n) = card(k: prime(n)^2 <= k < prime(n + 1)^2 and k term of A368458).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 2, 3, 3, 2, 5, 3, 3, 4, 5, 4, 3, 9, 5, 4, 7, 5, 6, 14, 6, 4, 7, 3, 5, 22, 6, 6, 4, 16, 5, 12, 12, 8, 15, 13, 5, 19, 5, 10, 4, 30, 26, 10, 6, 12, 11, 5, 28, 19, 15, 20, 8, 19, 9, 7, 22

Offset: 1

Peter Luschny, Dec 26 2023

If A368458 is written as an irregular triangle for n >= 3, then a(n) is the length of row n.

Conjecture: For all n >= 5, there is at least one j such that b(j) = 2 * (Bacher(j) - sigma(j)) + j + 1 is > 0 and prime(n)^2 < b(j) < prime(n + 1)^2. In other words, a(n) > 1 for n >= 5.

			a(11) = 5 because 31^2 = 961, 1073, 1147, 1271, 1333, 1369 = 37^2 and all the terms are in that order in A368458.

Cf. A000203, A001248, A050216 (Brocard's Conjecture), A368207 (Bacher), A368457, A368458.

# using A368207
def A368460(n):
    pn = nth_prime(n); pn1 = nth_prime(n + 1)
    A368457 = lambda n: 2 * (A368207(n) - sigma(n)) + n + 1
    return sum(1 for n in range(pn ** 2, pn1 ** 2) if A368457(n) > 0)
print([A368460(n) for n in range(1, 25)])

cp's OEIS Frontend

A368207 Bacher numbers: number of nonnegative representations of n = w*x+y*z with max(w,x) < min(y,z).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

CWEB

Julia

Mathematica

Python

Python

Python

Formula

A368276 Number of nonnegative representations of n = w*x + y*z with max(w, x) < min(y, z) and w <= x <= y <= z.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Julia

Mathematica

Python

A368458 Numbers k such that 2*(Bacher(k) - sigma(k)) + k + 1 > 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Julia

SageMath

Formula

A368459 Numbers k such that 2*(Bacher(k) - sigma(k)) + k + 1 < 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Julia

Formula

A368460 a(n) = card(k: prime(n)^2 <= k < prime(n + 1)^2 and k term of A368458).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

SageMath

A368207 Bacher numbers: number of nonnegative representations of n = wx+yz with max(w,x) < min(y,z).

A368276 Number of nonnegative representations of n = wx + yz with max(w, x) < min(y, z) and w <= x <= y <= z.