Weird numbers: Difference between revisions
no edit summary
No edit summary |
No edit summary |
||
Line 2,384:
Approx computation time: 284 ms</pre>
===My version===
Edit: I experimented a bit and created this second version. It's faster than the original, takes about 0.16 s for first 50.
::<syntaxhighlight lang="python"># anySum :: Int -> [Int] -> [Int]
""" Last updated 5/8/24 """
from itertools import combinations, takewhile
from math import prod
from time import time
start = time()
primitivesp_nos = {6} # No multiple of a semiperfect number is weird
def main(): # Range of nos [number1, number2]
weird_nos = []
n = 50 # Find n weird numbers
x = 1 # Number to be tested
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 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 """
fctrs = [] # Empty list
if n % 6 == 0: # 6 is primitive semiperfect, equals 2 * 3
return "Semiperfect"
while n % 2 == 0: # Divides by 2 (adds 2, 2...) to prime fctrs
fctrs.append(2) # Append 2
n //= 2
t = 2 ** (len(fctrs) + 1) - 1 # Test
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
for k in (i, i+2):
while n % k == 0:
while k <= t:
""" 2^k * p is never weird """
return "Semiperfect"
fctrs.append(k) # Append k
n //= k
i += 6
if n > 1:
fctrs.append(n) # Append n
return fctrs # Passes prime fctrs to isweird
def isweird(n): # Checks if n is weird
global primitivesp_nos # Retrieves list of primitive semiperfect nos
prime_fctrs = get_prime_fctrs(n)
if prime_fctrs == "Semiperfect":
return 0
sum_fctrs = 1 # Sum of all factors based on formula
fctrs = set(prime_fctrs) # Set of all fctrs
for i in fctrs:
sum_fctrs = sum_fctrs * (i ** (prime_fctrs.count(i) + 1) - 1)//(i - 1)
difference = sum_fctrs - n - n # Difference between sum of fctrs and target n
if difference < 0: # If difference < 0, n is deficient
return 0
if difference == 0: # If difference = 0, n is perfect
primitivesp_nos.add(n) # n is primitive semiperfect
return 0
for i in range(2, len(prime_fctrs)):
for j in combinations(prime_fctrs, i): # All combinations of prime fctrs
product = prod(j) # Product
if product not in primitivesp_nos: # Factor product added to set
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
if ns < 0:
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
for d in fctrs:
prime_fctrs |= prime_fctrs << d
if not prime_fctrs >> ns & 1: # Checks if combos set contains ns
return 1
else:
primitivesp_nos.add(n)
return 0
main() # Start program
end = time()
print("Execution time: ", round(end - start, 2), "s")
-- -> [100,96]</syntaxhighlight>
=={{header|Quackery}}==
| |||