A Python program for finding weird numbers

Python Help
1

This is my first post!

I just got into programming a couple months ago. I created a program for finding weird numbers (see Weird number - Wikipedia).

It takes about 0.3 s for first 50 weird numbers.

If you have any questions about how it works or suggestions (such as if this is in the wrong place), let me know!

from itertools import combinations
from sympy import divisors
from time import time

start = time() 

def main(): # Range of numbers [number1, number2]
    min = 1
    max = 26531 # below - Contains only weird numbers in range
    even = [i for i in range(min + min % 2, max, 2) if (i % 3 != 0 and isweird(i) == 1)] # No multiple of 20 is weird
    print("Even weird no:\n", even)
    if max > 10**21: # No odd weird numbers below 10^21
        if min < 10**21:
            min = int(10**21 + 1)
        odd = [i for i in range(min + min % 2 - 1, max, 2) if isweird(i) == i]
        print("Odd weird no: ", odd)
    
def isweird(n): # Filters nonweird numbers
    factors = divisors(n)
    factors.remove(n) # Creates list of factors of n, excluding n
    difference = sum(factors) - n 
    if difference <= 0: # If n is deficient or perfect, system exits 
        return
    sum_factors = 0
    factors.reverse()
    for i in factors: # Checks for obvious nonweird
        new = sum_factors + i # Stores new sum_factors in variable to save time 
        if new < n:
            sum_factors = new
        elif new == n:
            return
    included_factors = set(StopIteration if i <= difference else i for i in factors if i > difference) # Checks for factors that must be in combo that sums to n
    factors = [i for i in factors if i not in included_factors] 
    newsum = n - sum(included_factors) # New sum 
    for i in range(len(factors) - (n % 2) * ((n - sum(included_factors) - len(factors)) % 2),  1, -(n % 2 + 1)): # Combos that sum to n 
        for j in combinations(factors, i):
            if sum(j) == newsum:
                return 
    return 1 # Weird n is passed back to main

main()

end = time() 
print("Execution time: ", round(end - start, 2), "s")

Cyrus Polentschz

Below: nothing in particular - just wanted to share this program. It was moved to Python Help by a moderator.

2 Likes
3

it’s fixed

4

(Small nitpick: Your Wikipedia link includes the dot - for future examples, try having the dot outside the parentheses, or explicitly create your link with the [example link text](https://link.destination.example/) notation. For anyone who’s looking for the correct link, it’s here.)

The key here is the factors of the number. While it’s possible to test if a single number is weird, doing this for a large group of numbers (eg to find “the first N weird numbers”) should be able to take advantage of the repetition. In your example here, you query the divisors of each number completely independently; but you also have a min and max. So I’d start like this:

factors = defaultdict(list)
for factor in range(2, max):
    for multiple in range(factor + factor, max, factor):
        factors[multiple].append(factor)

There! Now you have all of those factors ready to go. You can then index into that instead of using divisors(), and it should be way WAY faster. (Note that this will not include self - for example, factors[12] is [2,3,4,6] without including 12. You could have it include that, but you were removing n itself, so it’s easier to just not include it in the first place. To change that behaviour, replace the “factor + factor” with just “factor”.)

I am a bit curious about this line.

included_factors = set(StopIteration if i <= difference else i for i in factors if i > difference)

StopIteration is just another value here. Since this is a set, you’ll only have one of that value, but it won’t halt the search. But I would also expect that it would bomb when you try to take that sum, which seems odd, since you didn’t mention that.

Hopefully that’ll help out a bit! Lemme know if there’s anything in particular you’re interested in here.

5

Thank you! I agree with your first suggestion about the dict. The line with the included_factors, the sum actually does work - when you run the program for, say, min = 1 and max = 10000 it actually does generate all 7 weird numbers in that range correctly.

For 10000 it returns:

Even weird no:
[70, 836, 4030, 5830, 7192, 7912, 9272]

which are the correct numbers that it should yield.

6

Nice little exercise. Here’s mine, also takes ~0.3 seconds. Will read yours next:

from sympy import divisors
from time import time

start = time() 

def main():
    show = 50
    n = 0
    while show:
        n += 1
        D = divisors(n)[:-1]
        if sum(D) > n:
            sums = 1
            for d in D:
                sums |= sums << d
            if not sums >> n & 1:
                print(n)
                show -= 1

main()

end = time() 
print("Execution time: ", round(end - start, 2), "s")

Attempt This Online!

7

Curious. Maybe it’s just never actually tripping. I didn’t delve too deep into it.

8

Yeah, that’s weird. The goal of that line was to search for factors that must be included in a combo for it to sum to n (in which case n isn’t weird.) If a specific factor is greater than the difference between sum(n), the sum of all factors of n except itself, and n, it must be included because the maximum possible sum of a factor combo if it were excluded would be sum(n) minus that factor, which is less than n.

My code

10

Updated program (replaced the line with the “StopIteration”). Still need to replace the sympy.divisors as Rosuav suggested. It’s faster than the original, which took ≈ 5 s for range 1 to 100000. This one takes 3. Plus for 1 to 300000, the original took 15 s, but this one takes 7 s.

from itertools import combinations, takewhile
from sympy import divisors
from time import time

start = time() 

def main(): # Range of numbers [number1, number2]
    min = 1
    max = 300000 # below - Contains only weird numbers in range
    weird_numbers = [i for i in range(min + min % 2, max, 2) if (i % 3 != 0 and isweird(i) == 1)] # No multiple of 6 is weird
    if max > 10**21: # No odd weird numbers below 10^21
        weird_numbers += [i for i in range(min + min % 2 - 1, max, 2) if isweird(i) == i]
        weird_numbers = sorted(weird_numbers)
    print("Weird numbers:\n", weird_numbers)
    
def isweird(n): # Filters nonweird numbers
    factors = divisors(n)
    factors.remove(n) # Creates list of factors of n, excluding n
    difference = sum(factors) - n 
    if difference <= 0: # If n is deficient or perfect, system exits 
        return
    sum_factors = 0
    factors.reverse()
    for i in factors: # Checks for obvious nonweird
        new = sum_factors + i # Stores new sum_factors in variable to save time 
        if new < n:
            sum_factors = new
        elif new == n:
            return
    included_factors = set(takewhile(lambda x:x > difference, factors)) # Checks for factors that must be in combo that sums to n
    factors = set(factors) - included_factors
    newsum = n - sum(included_factors) # New sum 
    for i in range(len(factors) - (n % 2) * ((n - sum(included_factors) - len(factors)) % 2),  1, -(n % 2 + 1)): # Combos that sum to n 
        for j in combinations(factors, i):
            if sum(j) == newsum:
                return 
    return 1 # Weird n is passed back to main

main()

end = time() 
print("Execution time: ", round(end - start, 2), "s")
12

Can you explain what these lines do? In your Attempt this Online code.

            sums = 1
            for d in D:
                sums |= sums << d
            if not sums >> n & 1:
                print(n)
                show -= 1
13

My sums is a bitset. Bit i means number i. For example sums = 33 would represent the set {0, 5}. Each new d can be added to each previous sum, and sums << d represents those new sums. And sums >> n & 1 checks whether the set of sums contains the sum n.

14

In other words, it’s equivalent to this:

            sums = {0}
            for d in D:
                sums |= {sum + d for sum in sums}
            if n not in sums:
                print(n)
                show -= 1
15

Improved program (using some of Stefan2’s and Rosuav’s advice/responses). It’s longer but faster. You have to input the upper limit. The program finds all weird numbers between 1 and the upper limit.

""" Last updated 5/8/24 """ 

from itertools import combinations, takewhile
from math import prod

primitivesp_nos = {6} # No multiple of a semiperfect number is weird

def main(): # Range of nos [number1, number2]
    print("This program prints all weird numbers between 1 and n.")
    max = int(input("Enter n, the upper limit: "))
    step = 2
    if max > 10**21: # No odd weird numbers below 10^21 
        step = 1 
    weird_nos = [i for i in range(2, max, step) if isweird(i) == 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 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 combos 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 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:
        return 0
    
main() # Start program
16

Can you please explain how calculating the first N weird numbers dependently rather than independently saves time and what this does? I understand the idea overall just not all the specific Python tools.

factors = defaultdict(list)
for factor in range(2, max):
    for multiple in range(factor + factor, max, factor):
        factors[multiple].append(factor)

Thank you!

17

This part is just looking at factors. The reason it’s faster is that, to compute the factors of N, you need only check the prime numbers up to its square root; and, in fact, you can extremely efficiently list all of the factors of a number by working upwards rather than downwards.

That is to say: Instead of computing the factors of N, we actually enumerate the multiples of every number up to the maximum. So we look at 2, and mark off every even number as having 2 as a factor; then look at 3, and mark off all multiples of three; and so on.

This is being done with a minimum of arithmetic - potentially just addition, not even multiplication, and certainly no expensive division or square rooting. The downside is that the entire collection has to be kept in memory.

18

Sounds like a good idea. So what you do is, for each number, you create a list of its multiples, then for each number you are testing you check which of these lists it belongs in?

19

Pretty much. The lists are indexed by the multiple, so it’s easy to pick up all of the factors of a number, but basically what you said, yeah.

20

and you only need to create those lists of multiples for prime numbers at or below the square root of maximum?

21

Actually that part is kinda inverted. Instead of building those lists up to the square root, you build them all the way to the number; but there won’t be any NEW factors after the square root.

22

But you only create lists of multiples for primes (i.e. 2, 3, 5, etc.), not 4 or 6?

23

Edit: missing an primitivesp_nos.add(n) after

if not prime_fctrs >> ns & 1: # Checks if combos set contains ns 
        return 1
    else: