A368458 -id:A368458 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

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

A368457 a(n) = 2(Bacher(n) - sigma(n)) + n + 1 = 2(A368207(n) - A000203(n)) + n + 1.

Original entry on oeis.org

2, 1, 0, 1, 0, -1, 0, -5, 2, -7, 0, -7, 0, -9, -4, -7, 0, -19, 0, -9, -10, -13, 0, -27, 4, -15, -12, -23, 0, -25, 0, -29, -14, -19, 0, -43, 0, -21, -16, -41, 0, -33, 0, -39, -28, -25, 0, -59, 6, -41, -20, -45, 0, -53, -16, -39, -22, -31, 0, -99, 0, -33, -20

Offset: 1

Peter Luschny, Dec 26 2023

sign

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 where max(w, x) < min(y, z).
Bacher's theorem shows that a(n) = 0 if n is an odd prime. Conversely, if a(n) = 0, we cannot conclude that n is prime as the example n = 35 shows, but this is probably the only exception.
Of the first 32,000 terms, approximately 88% are less than 0, 11% are equal to 0, and 1% are greater than 0. A368458 gives the indices for which a(n) is positive, and A368459 those for which a(n) is negative.
It appears that a(p^2) = p - 1 (A006093) for all prime p, following the observation by Knuth that apparently A368207(p^2) = (p^2 + 3*p)/2.

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

Cf. A000203, A001358, A001248, A006093, A368207, A368458, A368459, A368460.

using Nemo
A368457(n) = 2 * (A368207(n) - divisor_sigma(n, 1)) + n + 1
println([A368457(n) for n in 1:63])

t[n_]:=t[n]=Select[Divisors[n], #^2<=n&];
A368207[n_]:=Sum[(1+Boole[d^2A368457[n_]:=2(A368207[n]-DivisorSigma[1,n])+n+1;
Array[A368457, 100] (* Paolo Xausa, Jan 02 2024 *)

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.

cp's OEIS Frontend

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 = 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

A368457 a(n) = 2*(Bacher(n) - sigma(n)) + n + 1 = 2*(A368207(n) - A000203(n)) + n + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Julia

Mathematica

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Julia

Formula

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.

A368457 a(n) = 2(Bacher(n) - sigma(n)) + n + 1 = 2(A368207(n) - A000203(n)) + n + 1.