## 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.

Pages: 1 2

[…] 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 […]

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

here my commented solution: http://www.gleocadie.net/?p=519&lang=en

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)

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.

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";

}

Ok, maybe the code will look better like this

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]

New and improved! Now with formating!

A ruby version (kind of ugly though) …

in F#

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).

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;

}

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;

}

One more time. Really should have an edit option.