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.
Programming Praxis 
[…] 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):
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 . politeshere 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));;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.
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:]]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
#!/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"; }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!
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)) printA 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 endin 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) ]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; };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.
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; }