Talk:Weird numbers: Difference between revisions
No edit summary |
No edit summary |
||
(One intermediate revision by the same user not shown) | |||
Line 4: | Line 4: | ||
::<syntaxhighlight lang="python"># anySum :: Int -> [Int] -> [Int] |
::<syntaxhighlight lang="python"># anySum :: Int -> [Int] -> [Int] |
||
⚫ | |||
⚫ | |||
⚫ | |||
""" Last updated 5/8/24 """ |
|||
⚫ | |||
from math import prod |
from math import prod |
||
⚫ | |||
primitivesp_nos = set(); primes = [] |
|||
⚫ | |||
def main(): |
|||
primitivesp_nos = {6} # No multiple of a semiperfect number is weird |
|||
def main(): # Range of nos [number1, number2] |
|||
weird_nos = [] |
weird_nos = [] |
||
n = |
n = 1766 |
||
x = 1 |
x = 1 |
||
while n > 0: |
while n > 0: |
||
if isweird(x) == 1: |
if isweird(x) == 1: weird_nos.append(x); n = n - 1 |
||
⚫ | |||
⚫ | |||
x = x + 1 |
x = x + 1 |
||
print("First", len(weird_nos), "weird nos:\n", weird_nos) |
print("First", len(weird_nos), "weird nos:\n", weird_nos) |
||
⚫ | |||
def get_prime_fctrs(n): # Wheel factorization |
|||
⚫ | |||
""" Code from Jerome Richard """ |
|||
⚫ | |||
""" stackoverflow.com/questions/70635382/ |
|||
⚫ | |||
fastest-way-to-produce-a-list-of-all-divisors-of-a-number """ |
|||
if i * i > a: break |
|||
⚫ | |||
if n % 6 == 0: # 6 is primitive semiperfect, equals 2 * 3 |
|||
return |
if x == [n]: primes.append(n); return 0 |
||
sum_fctrs = 1; fctrs = set(x) |
|||
while n % 2 == 0: # Divides by 2 (adds 2, 2...) to prime fctrs |
|||
⚫ | |||
fctrs.append(2) # Append 2 |
|||
difference = sum_fctrs - 2 * n |
|||
⚫ | |||
t = 2 ** (len(fctrs) + 1) - 1 # Test |
|||
if difference == 0: primitivesp_nos.add(n) |
|||
while n % 3 == 0: # Divides by 3 (adds 3, 3...) to prime fctrs |
|||
fctrs.append(3) # Append 3 |
|||
n //= 3 |
|||
i = 5 |
|||
while i*i <= n: # Repeats above process |
|||
⚫ | |||
⚫ | |||
while k <= t: |
|||
""" 2^k * p is never weird """ |
|||
⚫ | |||
fctrs.append(k) # Append k |
|||
n //= k |
|||
i += 6 |
|||
if n > 1: |
|||
fctrs.append(n) # Append n |
|||
return fctrs # Passes prime fctrs to isweird |
|||
⚫ | |||
global primitivesp_nos # Retrieves list of primitive semiperfect nos |
|||
prime_fctrs = get_prime_fctrs(n) |
|||
if prime_fctrs == "Semiperfect": |
|||
return 0 |
return 0 |
||
⚫ | |||
sum_fctrs = 1 # Sum of all factors based on formula |
|||
⚫ | |||
fctrs = set(prime_fctrs) # Set of all fctrs |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
difference = sum_fctrs - n - n # Difference between sum of fctrs and target n |
|||
x = 1; fctrs = {1}.union(set(i for i in fctrs if i <= difference)) |
|||
if difference < 0: # If difference < 0, n is deficient |
|||
ns = n - (difference + n - sum(fctrs)) |
|||
if |
if ns < 0: return 1 |
||
⚫ | |||
⚫ | |||
return |
if not x >> ns & 1: return 1 |
||
⚫ | |||
⚫ | |||
for j in combinations(prime_fctrs, i): # All combinations of prime fctrs |
|||
product = prod(j) # Product |
|||
⚫ | |||
fctrs.add(product) |
|||
else: # If factor is semiperfect, n cannot be weird |
|||
return 0 |
|||
fctrs.add(1) # All numbers have 1 as a factor |
|||
fctrs = sorted(fctrs) # Sorts fctrs in order |
|||
fctrs = set(takewhile(lambda x:x <= difference, fctrs)) # Remaining fctrs set |
|||
ns = n - (difference + n - sum(fctrs)) # Stores in variable to save space |
|||
⚫ | |||
return 1 # n is weird |
|||
""" Code from Stefan2: |
|||
https://discuss.python.org/t/a-python-program-for- |
|||
finding-weird-numbers/48654/6 """ |
|||
prime_fctrs = 1 # Overwrites list, saves space |
|||
⚫ | |||
prime_fctrs |= prime_fctrs << d |
|||
if not prime_fctrs >> ns & 1: # Checks if combos set contains ns |
|||
return 1 |
|||
else: |
|||
⚫ | |||
return 0 |
|||
main() |
main() |
||
end = time() |
end = time() |
||
print("Execution time: ", round(end - start, 2), "s") |
print("Execution time: ", round(end - start, 2), "s") |
||
-- -> [100,96]</syntaxhighlight> |
-- -> [100,96]</syntaxhighlight> |
||
Latest revision as of 14:36, 29 May 2024
Longer but quicker version.
I saw there's already a Python program listed here for doing this, but I (with help from some others) created this one. Using the "sum of factors" formula it tests if a number is abundant BEFORE generating the list of each factors. If the number is deficient, the program returns so and saves memory. The program is alnmost twice as fast as the original, taking 0.16 s for the first 50.
# anySum :: Int -> [Int] -> [Int] from time import time start = time() from itertools import combinations from math import prod primitivesp_nos = set(); primes = [] def main(): weird_nos = [] n = 1766 x = 1 while n > 0: if isweird(x) == 1: weird_nos.append(x); n = n - 1 x = x + 1 print("First", len(weird_nos), "weird nos:\n", weird_nos) def isweird(n): global primes; global primitivesp_nos; x = []; a = n for i in primes: while a % i == 0: x.append(i); a = a//i if i * i > a: break if a > 1: x.append(a) if x == [n]: primes.append(n); return 0 sum_fctrs = 1; fctrs = set(x) for i in fctrs: sum_fctrs = sum_fctrs*(i**(x.count(i)+1)-1)//(i-1) difference = sum_fctrs - 2 * n if difference <= 0: if difference == 0: primitivesp_nos.add(n) return 0 for i in range(2, len(x)): for j in combinations(x, i): product = prod(j) if product not in primitivesp_nos: fctrs.add(product) else: return 0 x = 1; fctrs = {1}.union(set(i for i in fctrs if i <= difference)) ns = n - (difference + n - sum(fctrs)) if ns < 0: return 1 for d in fctrs: x |= x << d if not x >> ns & 1: return 1 else: primitivesp_nos.add(n); return 0 main() end = time() print("Execution time: ", round(end - start, 2), "s") -- -> [100,96]
A faster and less ambitious algorithm ?
I noticed yesterday that entries here were sparse.
Perhaps some were abandoned after first-sketch exhaustive searches appeared interminably slow ? And possibly the references to number theory in the Perl 6 founding example could look a bit daunting to some ?
Here is a theoretically unambitious approach, which seems, for example, to compress the (functionally composed) Python version down to c. 300 ms for 50 weirds (about half that for 25 weirds), on a system which needs c. 24 seconds to find 25 weirds with the initial Perl 6 draft.
- Choose a smaller target for the sum-search.
- Use a recursive hasSum(target, divisorList) predicate which fails early.
- Generate the properDivisors in descending order of magnitude.
A smaller target should, I think, involve a smaller number of possible sums. The obvious candidate in an abundant number is the difference between the sum of the proper divisors and the number considered. If a sum to that difference exists, then removing the participants in the smaller sum will leave a set which sums to the abundant number itself.
For possible early-failing implementations of hasSum, see the Python, Haskell, JavaScript and even AppleScript drafts.
If hasSum considers large divisors first, it can soon exclude all those those too big to sum to a smaller target. Hout (talk) 11:52, 24 March 2019 (UTC)
- PS I think we may be able to see and test the operation of hasSum more clearly if we enrich its type from Bool to [Int] (with a return value of the empty list for False, and the integers of the first sum found for True). Let's call this richer-typed variant anySum, and sketch it in Python 3.
# anySum :: Int -> [Int] -> [Int] def anySum(n, xs): '''First subset of xs found to sum to n. (Probably more efficient where xs is sorted in descending order of magnitude)''' def go(n, xs): if xs: # Assumes Python 3 for list deconstruction # Otherwise: h, t = xs[0], xs[1:] h, *t = xs if n < h: return go(n, t) else: if n == h: return [h] else: ys = go(n - h, t) return [h] + ys if ys else go(n, t) else: return [] return go(n, xs) # Search for sum through descending numbers (more efficient) print(anySum(196, range(100, 0, -1))) # -> [100, 96] # Search for sum through ascending numbers (less efficient) print(anySum(196, range(1, 101))) # -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 25] print(anySum(7, [6, 3])) # -> []
or similarly, rewriting hasSum to anySum (with comments) in a Haskell idiom:
module AnySum where hasSum :: Int -> [Int] -> Bool hasSum _ [] = False hasSum n (x:xs) | n < x = hasSum n xs | otherwise = (n == x) || hasSum (n - x) xs || hasSum n xs -- Or, enriching the return type from Bool to [Int] -- with [] for False and a populated list (first sum found) for True anySum :: Int -> [Int] -> [Int] anySum _ [] = [] anySum n (x:xs) | n < x = anySum n xs -- x too large for a sum to n | n == x = [x] -- We have a sum | otherwise = let ys = anySum (n - x) xs -- Any sum for (n - x) in the tail ? in if null ys then anySum n xs -- Any sum (not involving x) in the tail ? else x : ys -- x and the rest of the sum that was found. main :: IO () main = do -- xs ascending - the test is less efficient print $ anySum 196 [1 .. 100] -- -> [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,25] -- xs descending - the test is more efficent print $ anySum 196 [100,99 ..] -- -> [100,96]