Polite Numbers

December 17, 2010

A number is polite if it can be written as the sum of two or more consecutive numbers; for instance, 7 is polite because it can be written at 3 + 4. Some numbers can be written as the sum of two or more consecutive numbers in more than one way; for instance, 15 = 1 + 2 + 3 + 4 + 5 = 4 + 5 + 6 = 7 + 8. The number of ways that a number can be written as the sum of two or more consecutive numbers is its politeness. Any number that is a power of 2 cannot be written as the sum of two or more consecutive numbers; such a number has a politeness of 0, and is thus impolite.

There is a set of consecutive integers that sum to a given number for each odd divisor of the number greater than 1. For instance, the divisors of 28 are 1, 2, 4, 7, 14, 28. The only odd divisor of 28 greater than 1 is 7, so 28 has a politeness of 1. The set of consecutive integers has length 7 (the divisor) and is centered at 4 = 28 ÷ 7: 1 + 2 + 3 + 4 + 5 + 6 + 7; that works because there are 7 numbers with an average of 4 (since they are centered on 4). In some cases, such as the divisor 11 of the number 33, the set of numbers includes negative integers: -2 + -1 + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8; in that case, the negative integers cancel out the corresponding positive integers, so the remaining set is 3 + 4 + 5 + 6 + 7 + 8 = 33.

Your task is to write a program that calculates all the ways that a number can be written as the sum of two or more consecutive numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

15 Responses to “Polite Numbers”

  1. [...] Praxis – Polite Numbers By Remco Niemeijer In today’s Programming Praxis exercise, our task is to list all the ways that a number can be written as the [...]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2010/12/17/programming-praxis-polite-numbers/ for a version with comments):

    import Data.List
    import Data.Numbers.Primes
    
    divisors :: Integral a => a -> [a]
    divisors = nub . sort . map product . subsequences . primeFactors
    
    polites :: Integral a => a -> [[a]]
    polites n = [ [max (d//2 - n//d + 1) (n//d - d//2)..n//d + d//2]
                | d <- tail $ divisors n, odd d, let (//) = div]
    
    politeness :: Integral a => a -> Int
    politeness = length . polites
    
  3. here my commented solution: http://www.gleocadie.net/?p=519&lang=en

    open List;;
    
    let seq lb ub =
      let rec seq' n res =
        if n >= lb
          then seq' (n-1) (n::res)
          else res
    in seq' ub [];;
    
    let divisors n =
      let module S = Set.Make(struct type t = int let compare = compare end) in
      S.elements (fold_left
                    (fun x -> fun y -> if n mod y = 0
                                         then S.add y x
                                         else x) S.empty (seq 1 n));;
    let polite n =
      let odd1p = (fun x -> x > 1 && x mod 2 = 1) in
      map (fun d -> let y = n / d
                     and d' = d / 2 in
                       seq (max (d' - y + 1) (y - d')) (y + d'))
          (filter odd1p (divisors n));;
    
  4. Tom said

    Hi,
    Here’s my solution in Scala. I’m sure there’s a better way to calculate divisors and also a better way to expand the length of array rather than just incrementing it.


    import scala.collection.mutable._

    object Divisors
    {
    def generate(n:Int) =
    {
    var divisors = ListBuffer[Int]()
    for(i <- 1 to n)
    {
    if(n % i == 0)
    divisors += i
    }
    divisors.toList
    }
    }

    object PoliteNumbers
    {
    def calculate(number:Int) =
    {
    var politeness = 0
    for(divisor 1 && divisor < number && divisor % 2 == 1)
    {
    politeness += 1
    var start = divisor
    var end = divisor
    var sum = 0
    while(sum < number)
    {
    start -= 1
    end += 1
    sum = (start to end).sum
    }
    println(start+" to "+end+" : "+(start to end).sum)
    }
    }
    println("Politeness is "+politeness)
    }

    }
    val number = Integer.parseInt(args(0))
    PoliteNumbers.calculate(number)

  5. Graham said

    Brain’s a little worn out from moving/end of semester, so I Pythoned the Scheme procedures.
    I don’t think that we need to check whether n is a power of 2, because it will have no odd
    divisors if it is.

    
    def ilog(b, n):
        c = 0
        i = b
        while i <= n:
            c += 1
            i *= b
        return c
    
    def odd_divisors(n):
        return [d for d in xrange(1, n + 1) if d % 2 and not n % d]
    
    def politeness(n):
        return len(odd_divisors(n)) - 1
    
    def polite(n, d):
        d2 = d//2
        nd = n//d
        if d2 < nd:
            return range(nd - d2, nd + d2 + 1)
        else:
            return range(abs(nd - d2) + 1, (nd + d2 + 1))
    
    def polites(n):
        return [polite(n, d) for d in odd_divisors(n)[1:]]
    
  6. ye said

    Here is a Perl solution. I hope I uploaded the code correctly


    #!/usr/bin/perl

    print "Enter an integer: ";
    $number = ;
    chomp($number);

    $politeness = 0;

    for($div = 3; $div <= $number; $div += 2) { #iterate through odd potential divisors
    if($number % $div == 0) { #found an odd divisor
    $codiv = $number / $div; #set the codivisor
    printline($codiv-($div-1)/2,$div);
    $politeness++;
    }
    }
    print "Politeness of $number is $politeness\n";

    sub printline
    {
    my $base = $_[0];
    my $count = $_[1];
    if($base < 0) { #cancel off the negative part
    $base = -$base + 1;
    $count = $count - (2*$base) + 1;
    }
    print "$base";
    $count--;
    until($count == 0){
    $base++;
    print " + $base";
    $count--;
    }
    print " = $number\n";
    }

  7. ye said

    Ok, maybe the code will look better like this

    #!/usr/bin/perl
    
    print "Enter an integer: ";
    $number = <STDIN>;
    chomp($number);
    
    $politeness = 0;
    
    for($div = 3; $div <= $number; $div += 2) { #iterate through odd potential divisors
      if($number % $div == 0) { #found an odd divisor
        $codiv = $number / $div; #set the codivisor
        printline($codiv-($div-1)/2,$div);
        $politeness++;
      }
    }
    print "Politeness of $number is $politeness\n";
    
    sub printline 
    {
      my $base = $_[0];
      my $count = $_[1];
      if($base < 0) { #cancel off the negative part
        $base = -$base + 1;
        $count = $count - (2*$base) + 1;
      }
      print "$base";
      $count--;
      until($count == 0){
        $base++;
        print " + $base";
        $count--;
      }
      print " = $number\n";
    }
    
  8. Mike said

    a “functional” python version

    factors(n) returns a sequence of (p,k) tuples, where p^k is in the factorization of “n”

    from itertools import dropwhile, imap, islice, product, repeat, starmap
    from operator import mul

    def geometric_series(p, k):
    ”’return generator for geometric series p^0, p^1, p^2, … p^k.”’

    return (pow(p, n) for n in range(k+1))

    def odd_divisors(n):
    ”’generates all odd divisors of “n”.”’

    odd_factors = dropwhile(lambda t:t[0]&1==0, factors(n))
    sets_of_odd_factors = product(*starmap(geometric_series, odd_factors))
    return imap(reduce, repeat(mul), sets_of_odd_factors, repeat(1))

    def polites(n):
    ”’generates lists of consecutive integers that sum to “n”.”’

    for divisor in islice(odd_divisors(n), 1, None):
    hi = n/divisor + divisor/2
    low = max(hi – divisor + 1, divisor – hi)

    yield range(low,hi+1)

    def politeness(n):
    ”’return number of sequences that sum to “n”.”’

    return sum(imap(bool, odd_divisors(n))) – 1

    #test:
    for n in (28, 33, 42, 64):
    print ‘the politeness of %d is %d:’ % (n, politeness(n))
    for lst in polites(n):
    print ‘ %s = %d’ % (‘ + ‘.join(str(i) for i in lst), sum(lst))
    print

    [/soucecode]

  9. Mike said

    New and improved! Now with formating!

    from itertools import dropwhile, imap, islice, product, repeat, starmap
    from operator import mul
    
    def geometric_series(p, k):
        '''return generator for geometric series p^0, p^1, p^2, ... p^k.'''
        return (pow(p, n) for n in range(k+1))
    
    def odd_divisors(n):
        odd_factors = dropwhile(lambda t:t[0]&1==0, factors(n))
        sets_of_odd_factors = product(*starmap(geometric_series, odd_factors))
        return imap(reduce, repeat(mul), sets_of_odd_factors, repeat(1))
    
    def polites(n):
        for divisor in islice(odd_divisors(n), 1, None):
            hi = n/divisor + divisor/2
            low = max(hi - divisor + 1, divisor - hi)
    
            yield range(low,hi+1)
    
    def politeness(n):
        return sum(imap(bool, odd_divisors(n))) - 1
    
    #test
    for n in (28, 33, 42, 64):
        print 'the politeness of %d is %d:' % (n, politeness(n))
        for lst in polites(n):
            print '   %s = %d' % (' + '.join(str(i) for i in lst), sum(lst))
        print
    
  10. slabounty said

    A ruby version (kind of ugly though) …

    class Integer
        def divisors
            d = []
            1.upto(Math.sqrt(self)) do | i |
                if self % i == 0
                    d << i
                    d << self / i
                end
            end
            d
        end
    
        def politeness_sums
            d = self.divisors
            d.sort.each do |dv|
                if dv != 1 && dv != self && (dv % 2 != 0)
                    center = self/dv
                    b = center - dv/2
                    b = b.abs + 1 if b < 0
                    e = center + dv/2
                    yield Range.new(b, e)
                end
            end
        end
    end
    
    28.politeness_sums do |ps| 
        print "28 = "
        ps.each { |v| print (v==ps.first ? "#{v}" : " + #{v}") }
        puts
    end
    33.politeness_sums do |ps| 
        print "33 = "
        ps.each { |v| print (v==ps.first ? "#{v}" : " + #{v}") }
        puts
    end
    
  11. Khanh Nguyen said

    in F#

    open System
    
    let generate_set (center:int) (length:int) = 
        let upper = center + length / 2
        let lower = center - length / 2
        List.append [lower..center] [center+1..upper] 
    let polite_number (n:int) = 
        [
            for i in 2 .. n do 
                if n % i = 0 && i % 2 = 1 then
                    yield (generate_set (n/i) i)
        ]
    
  12. Here’s a non-optimal method written in JavaScript. Computational time is O(n/2).

    The function will return a 2d array; first value is the starting number, second value is the number of steps that need to be taken. For example if checkNum() returns [[1, 4]] this means to start at 1 and add a total of 4 numbers together in sequence (e.g. 1+2+3+4).

    function checkNum(N){
    	var result = [], i = 2, P;
    	do{
    		P = N / i + (1 - i) / 2;
    		if(Math.floor(P) === P) result.push([P, i]);
    		i++;
    	}while(P >= 2);
    	return result;
    };
    
  13. Bryan Elliott said

    JS Solve:
    function checkNum(N) {
    //We will return arrays of [start, ct]
    var results = [],
    //Longest possible sequence count is 1+2+3+4+…
    //For a given sequence length ct, this is N=(ct^2+ct)/2
    //Solving for ct, we find that the longest possible sequence is…
    maxCt = Math.ceil((Math.sqrt(8*N+1)-1)/2),
    //If N is even, ct cannot be 2.
    ct = ((N&1)==0)?3:2,
    center, frac;
    for (;ct<=maxCt;ct++) {
    center=N/ct, frac=center-Math.floor(center);
    if (
    //we've divided evenly into a sequence of ct (odd
    (frac==0 && (ct&1)==1) ||
    // or even)
    (frac==0.5 && (ct&1)==0)
    ) {
    results.push([center-(ct-1)/2, ct]);
    }
    }
    return results;
    }

  14. Bryan Elliott said

    Trying again, after reading the help…

    function checkNum(N) {
    //We will return arrays of [start, ct]
    var results = [],
    //Longest possible sequence count is 1+2+3+4+...;
    //For a given sequence length ct, this is N=(ct^2+ct)/2
    //Solving for ct, we find that the longest possible sequence is...
    maxCt = Math.ceil((Math.sqrt(8*N+1)-1)/2),
    //If N is even, ct cannot be 2.
    ct = ((N&1)==0)?3:2,
    center, frac;
    for (;ct<=maxCt;ct++) {
    center=N/ct, frac=center-Math.floor(center);
    if (
    //we've divided evenly into a sequence of ct (odd
    (frac==0 && (ct&1)==1) ||
    // or even)
    (frac==0.5 && (ct&1)==0)
    ) {
    results.push([center-(ct-1)/2, ct]);
    }
    }
    return results;
    }

  15. Bryan Elliott said

    One more time. Really should have an edit option.

    function checkNum(N) {
    	//We will return arrays of [start, ct]
    	var results = [],
    		//Longest possible sequence count is 1+2+3+4+...;
    		//For a given sequence length ct, this is N=(ct^2+ct)/2
    		//Solving for ct, we find that the longest possible sequence is...
    		maxCt = Math.ceil((Math.sqrt(8*N+1)-1)/2),
    		//If N is even, ct cannot be 2.
    		ct = ((N&1)==0)?3:2,
    		center, frac;
    	for (;ct<=maxCt;ct++) {
    		center=N/ct, frac=center-Math.floor(center);
    		if (
    			//we've divided evenly into a sequence of ct (odd
    			(frac==0 && (ct&1)==1) ||
    			// or even)
    			(frac==0.5 && (ct&1)==0)
    		) {
    			results.push([center-(ct-1)/2, ct]);
    		}
    	}
    	return results;
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 599 other followers

%d bloggers like this: