4
\$\begingroup\$

This is from Wikipedia:

In mathematics, Waring's prime number conjecture is a conjecture in number theory, closely related to Vinogradov's theorem. The conjecture is named after the English mathematician Edward Waring and states that every odd integer exceeding 3 is either a prime number or the sum of three prime numbers. The conjecture is known to follow from the generalized Riemann hypothesis.

My code:

 def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

def prime_number(maximum):
  number_list=(i for i in range(1,maximum+1))
  divisor=1
  divisor_list=[]
  prime_number_list=[]
  for e in number_list:
    while divisor<=e:
      if e%divisor==0:
        divisor_list.append(divisor_list)
        divisor+=1
      else:
        divisor+=1
    if len(divisor_list)==2:
      prime_number_list.append(e)
      prime_number_list.append(e)
      prime_number_list.append(e)
      prime_number_list.append(e)
      divisor=1
      divisor_list=[]
    else:
      divisor=1
      divisor_list=[]
  return prime_number_list


def div_by_two(num):
  if num%2==0:
    return False
  else:
    return True

def Waring_Number(maximum):
  input_list=range(5,maximum+1)
  combination_of_prime_number=combinations(prime_number(maximum),3)
  prime_number_list=prime_number(maximum)
  odd_number=[i for i in input_list if div_by_two(i)]
  for e in odd_number:
    if e in prime_number_list:
      print ("{} is a prime number.".format(e))
    else:
        for combination in combination_of_prime_number:
          if sum(combination)==e:
            print ("{}+{}+{}={}".format(combination[0],combination[1],combination[2],e))
            break

Few Notes:

  • I just copied and pasted the combination function from itertools documentation, I do not know how the function actually works, only how it works.

  • prime_number_list.append(e) was repeated four times because the combinations had to include prime numbers being repeated three times too. (For example, (3,3,3) has to be created for Waring Number to work) I know this takes up time.

  • I am a beginner. I have only been doing Python for few months for hobby and only know the basics

Any and all feedback is welcome.

\$\endgroup\$
  • 2
    \$\begingroup\$ Is there a reason you copy/pasted combinations instead of just importing it? \$\endgroup\$ – User319 Jan 28 '17 at 17:13
  • \$\begingroup\$ Because I thought itertool only worked in Python 2 and I was working on Python 3. \$\endgroup\$ – Phil Jan 28 '17 at 17:16
  • 2
    \$\begingroup\$ Nah. docs.python.org/3/library/itertools.html#itertools.combinations. They just took some stuff out that was made redundant due to other update, I believe \$\endgroup\$ – User319 Jan 28 '17 at 17:19
2
\$\begingroup\$

Naming. Mostly good. You're making the effort to be descriptive with it, which is awesome. I would change odd_number to odd_numbers since it's a list. Also, prime_number really tells me nothing about what the function is actually doing. Not going to suggest an alternative name, because I'll have more to say about this function later. Warring_Number violates PEP 8. (warring_number instead.)

More, descriptive functions. This can make it easier to get a high-level understanding of what's going on when you're reading it. For example, at the start of warring_number, you could do odd_numbers = get_odd_numbers_in_interval(5, maximum). More importantly though, in your prime_number function, you can just do:

for e in number_list:
    if is_prime(e):
        #etc.

This not only makes it more clear what you're doing. You're also making it so that when you want to speed up checking if a number is prime, you don't have to worry about how that logic will affect anything else. It's all right in one place.

Speaking of...

Avoid brute force. If you finding yourself iterating over every single possibility, it's usually worth it to see if there's a clever way to speed things up. Checking if a number is prime has been researched a lot, so I would just go to Wikipedia or StackOverflow and use an algorithm that I'm not smart enough to come up with myself. For checking if a number is a sum of three primes, let's think about it.

Right now, your check for, say, 13 looks something like this:

2 + 2 + 2 = 6
2 + 2 + 3 = 7
2 + 2 + 5 = 9
2 + 2 + 7 = 11
2 + 2 + 11 = 15
etc.

Let's do it manually, and apply a bit of thought.

for i in list_of_primes:
    for j in list_of_primes:

At this point, there is a unique number x such that i + j + x = e. So let's just check that and move on

        if is_prime(e - (i + j)):

More on prime_numbers: I really don't like that it returns 4 values of each prime. It's not an obvious thing to do, and I would prefer to have the calling code manipulate the return value so it looks like it needs to. In any case, you already have a use for the function where you don't want duplicates of every prime. Additionally, it is a rather expensive function, and you call it twice. Instead, you could do:

prime_number_list = prime_number(maximum)
combination_of_prime_number = combinations(prime_number_list, 3)

Style comments: Spaces around operators, please. if e % divisor == 0 is much easier to read than if e%divisor==0.

Instead of

if boolean:
    return False
else:
    return True

You can just do:

return not boolean

Actually, I believe this is a bug in div_by_two. It should just be

def div_by_two(n):
    if n % 2 == 0:
        return True
    else:
        return False

Which would simplify to

def div_by_two(n):
    return n % 2 == 0
\$\endgroup\$
  • \$\begingroup\$ The code looks much cleaner and runs much faster, thanks for the advice. \$\endgroup\$ – Phil Jan 29 '17 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.