## Polite Numbers

### December 17, 2010

The list of numbers corresponding to the odd divisor *d* of the number *n* is calculated by the `polite`

function; the first arm of the `if`

is the “normal” case, and the second arm of the `if`

is taken when the list includes 0 or negative numbers:

`(define (polite n d)`

(let ((d2 (quotient d 2)) (n/d (/ n d)))

(if (< d2 n/d)

(range (- n/d d2) (+ n/d d2 1))

(range (+ (abs (- n/d d2)) 1) (+ n/d d2 1)))))

We make a list of all the sets of consecutive integers by iterating through the odd divisors of the input number:

`(define (polites n)`

(if (= (expt 2 (ilog 2 n)) n) '()

(let loop ((ds (cdr (filter odd? (divisors n)))) (ps '()))

(if (null? ds) (reverse ps)

(loop (cdr ds) (cons (polite n (car ds)) ps))))))

It’s easy to compute the politeness of a number:

`(define (politeness n)`

(if (= (expt 2 (ilog 2 n)) n) 0

(length (cdr (filter odd? (divisors n))))))

Here are some examples:

`> (politeness 15)`

3

> (polites 15)

((4 5 6) (1 2 3 4 5) (7 8))

> (politeness 28)

1

> (polites 28)

((1 2 3 4 5 6 7))

> (politeness 33)

3

> (polites 33)

((10 11 12) (3 4 5 6 7 8) (16 17))

We used range, filter, sort, unique, and ilog from the Standard Prelude, and `factors`

and `divisors`

from a previous exercise. You can run the program at http://programmingpraxis.codepad.org/YgFEcg8Q.

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.