Weird numbers: Difference between revisions

Content added Content deleted
No edit summary
mNo edit summary
Line 2,416: Line 2,416:
fastest-way-to-produce-a-list-of-all-divisors-of-a-number """
fastest-way-to-produce-a-list-of-all-divisors-of-a-number """
fctrs = [] # Empty list
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
while n % 2 == 0: # Divides by 2 (adds 2, 2...) to prime fctrs
fctrs.append(2) # Append 2
fctrs.append(2) # Append 2
n //= 2
n //= 2
t = 2 ** (len(fctrs) + 1) - 1 # Test
while n % 3 == 0: # Divides by 3 (adds 3, 3...) to prime fctrs
while n % 3 == 0: # Divides by 3 (adds 3, 3...) to prime fctrs
fctrs.append(3) # Append 3
fctrs.append(3) # Append 3
Line 2,429: Line 2,426:
for k in (i, i+2):
for k in (i, i+2):
while n % k == 0:
while n % k == 0:
while k <= t:
""" 2^k * p is never weird """
return "Semiperfect"
fctrs.append(k) # Append k
fctrs.append(k) # Append k
n //= k
n //= k
Line 2,441: Line 2,435:
def isweird(n): # Checks if n is weird
def isweird(n): # Checks if n is weird
global primitivesp_nos # Retrieves list of primitive semiperfect nos
global primitivesp_nos # Retrieves list of primitive semiperfect nos
⚫
if n % 6 == 0: # 6 is primitive semiperfect, equals 2 * 3
⚫
prime_fctrs = get_prime_fctrs(n)
if prime_fctrs == "Semiperfect":
return 0
return 0
⚫
x = get_prime_fctrs(n)
sum_fctrs = 1 # Sum of all factors based on formula
sum_fctrs = 1 # Sum of all factors based on formula
fctrs = set(prime_fctrs) # Set of all fctrs
fctrs = set(x) # Set of all fctrs
for i in fctrs:
for i in fctrs:
sum_fctrs = sum_fctrs * (i ** (prime_fctrs.count(i) + 1) - 1)//(i - 1)
sum_fctrs = sum_fctrs * (i ** (x.count(i) + 1) - 1)//(i - 1)
difference = sum_fctrs - n - n # Difference between sum of fctrs and target n
difference = sum_fctrs - n - n # Difference between sum of fctrs and target n
if difference < 0: # If difference < 0, n is deficient
if difference <= 0: # If difference < 0, n is deficient
return 0
if difference == 0:
⚫
primitivesp_nos.add(n)
if difference == 0: # If difference = 0, n is perfect
⚫
return 0
⚫
primitivesp_nos.add(n) # n is primitive semiperfect
return 0
for i in range(2, len(x)):
for i in range(2, len(prime_fctrs)):
for j in combinations(x, i): # All combinations of prime fctrs
for j in combinations(prime_fctrs, i): # All combinations of prime fctrs
product = prod(j) # Product
product = prod(j) # Product
if product not in primitivesp_nos: # Factor product added to set
if product not in primitivesp_nos: # Factor product added to set
Line 2,461: Line 2,454:
else: # If factor is semiperfect, n cannot be weird
else: # If factor is semiperfect, n cannot be weird
return 0
return 0
⚫
x = 1 # Overwrites list, saves space
fctrs.add(1) # All numbers have 1 as a factor
fctrs.add(1) # All numbers have 1 as a factor
fctrs = sorted(fctrs) # Sorts fctrs in order
fctrs = sorted(fctrs) # Sorts fctrs in order
Line 2,470: Line 2,464:
https://discuss.python.org/t/a-python-program-for-
https://discuss.python.org/t/a-python-program-for-
finding-weird-numbers/48654/6 """
finding-weird-numbers/48654/6 """
⚫
prime_fctrs = 1 # Overwrites list, saves space
for d in fctrs:
for d in fctrs:
prime_fctrs |= prime_fctrs << d
x |= x << d
if not prime_fctrs >> ns & 1: # Checks if combos set contains ns
if not x >> ns & 1: # Checks if combos set contains ns
return 1
isweird = 1
else:
else:
primitivesp_nos.add(n)
primitivesp_nos.add(n)
return 0
isweird = 0
return isweird
main() # Start program
main() # Start program
Retrieved from "https://rosettacode.org/wiki/Weird_numbers"