Post Reply 
(28 48 49 50) Bernoulli Numbers
09-09-2023, 07:34 PM (This post was last modified: 09-10-2023 05:33 PM by Albert Chan.)
Post: #9
RE: (28 48) Bernoulli numbers
(09-09-2023 06:33 PM)Albert Chan Wrote:  By design (blue region), p factors <= q factors
We keep 1 factor, if p=q, to avoid double counting.
Since we start off half p's first, half q's loop will quit if p >= q.

Simpler version, removed test for p >= q
We know halfp loops, n = 2^m-1 had halfp factors completely removed.
Test for prime if q=p, n%q==0 is false, thus no double counting factors.

max(p factors) ≤ min(q factors)
hi + 1 ≤ m / hi + 1
hi^2 ≤ m
hi ≤ √m

Code:
function min_d(m) -- B(even m>=2) reduced denominator
    local n, d, hi = 2^m-1, 1, sqrt(m)
    for p = 3, hi+1, 2 do               -- half p's
        if n%p ~= 0 then continue end
        repeat n = n/p until n%p ~= 0
        if m%(p-1)==0 then d = d*p end  -- m = (p-1)*(q-1)
    end
    for k = 1, hi do
        local q = m/k + 1               -- half q's
        if m%k==0 and n%q==0 then d = d*q end
    end
    return 2*d
end

if we set hi = m, and remove k loops, we get back O(m) version.
Benchmarks suggested O(√m) version is faster for even m ≥ 12
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: (48G) Bernoulli numbers - Gerald H - 09-06-2023, 08:48 AM
RE: (48G) Bernoulli numbers - John Keith - 09-06-2023, 11:04 AM
RE: (48G) Bernoulli numbers - Gerald H - 09-06-2023, 02:34 PM
RE: (48G) Bernoulli numbers - Albert Chan - 09-07-2023, 03:37 PM
RE: (48G) Bernoulli numbers - John Keith - 09-07-2023, 04:18 PM
RE: (28 48) Bernoulli numbers - Albert Chan - 09-09-2023 07:34 PM
RE: (28 48) Bernoulli numbers - John Keith - 09-08-2023, 08:09 PM
RE: (28 48) Bernoulli numbers - John Keith - 09-10-2023, 03:24 PM
RE: (28 48) Bernoulli numbers - John Keith - 09-10-2023, 07:45 PM



User(s) browsing this thread: 2 Guest(s)