Proper divisors: Difference between revisions
No edit summary |
Walterpachl (talk | contribs) m (typo) |
||
Line 1: | Line 1: | ||
{{draft task}} |
{{draft task}} |
||
The [http://planetmath.org/properdivisor proper divisors] of a positive integer N are those numbers, other than N itself, that divide N without remainder. <br>For N > 1 they will always include 1, but for N == 1 |
The [http://planetmath.org/properdivisor proper divisors] of a positive integer N are those numbers, other than N itself, that divide N without remainder. <br>For N > 1 they will always include 1, but for N == 1 there are no proper divisors. |
||
For example the proper divisors of 6 are 1, 2, and 3. The proper divisors of 100 are 1, 2, 4, 5, 10, 20, 25, and 50. |
For example the proper divisors of 6 are 1, 2, and 3. The proper divisors of 100 are 1, 2, 4, 5, 10, 20, 25, and 50. |
Revision as of 11:42, 19 January 2016
The proper divisors of a positive integer N are those numbers, other than N itself, that divide N without remainder.
For N > 1 they will always include 1, but for N == 1 there are no proper divisors.
For example the proper divisors of 6 are 1, 2, and 3. The proper divisors of 100 are 1, 2, 4, 5, 10, 20, 25, and 50.
- Task
- Create a routine to generate all the proper divisors of a number.
- use it to show the proper divisors of the numbers 1 to 10 inclusive.
- Find a number in the range 1 to 20,000 with the most proper divisors. Show the number and just the count of how many proper divisors it has.
Show all output here.
- Cf.
- Amicable pairs
- Abundant, deficient and perfect number classifications
- Aliquot sequence classifications
- Factors of an integer
- Prime decomposition
AWK
<lang AWK>
- syntax: GAWK -f PROPER_DIVISORS.AWK
BEGIN {
show = 0 # show divisors: 0=no, 1=yes print(" N cnt DIVISORS") for (i=1; i<=20000; i++) { divisors(i) if (i <= 10 || i == 100) { # including 100 as it was an example in task description printf("%5d %3d %s\n",i,Dcnt,Dstr) } if (Dcnt < max_cnt) { continue } if (Dcnt > max_cnt) { rec = "" max_cnt = Dcnt } rec = sprintf("%s%5d %3d %s\n",rec,i,Dcnt,show?Dstr:"divisors not shown") } printf("%s",rec) exit(0)
} function divisors(n, i) {
if (n == 1) { Dcnt = 0 Dstr = "" return } Dcnt = Dstr = 1 for (i=2; i<n; i++) { if (n % i == 0) { Dcnt++ Dstr = sprintf("%s %s",Dstr,i) } } return
} </lang>
output:
N cnt DIVISORS 1 0 2 1 1 3 1 1 4 2 1 2 5 1 1 6 3 1 2 3 7 1 1 8 3 1 2 4 9 2 1 3 10 3 1 2 5 100 8 1 2 4 5 10 20 25 50 15120 79 divisors not shown 18480 79 divisors not shown
C
C has tedious boilerplate related to allocating memory for dynamic arrays, so we just skip the problem of storing values altogether. <lang c>
- include <stdio.h>
- include <stdbool.h>
int proper_divisors(const int n, bool print_flag) {
int count = 0;
for (int i = 1; i < n; ++i) { if (n % i == 0) { count++; if (print_flag) printf("%d ", i); } }
if (print_flag) printf("\n");
return count;
}
int main(void) {
for (int i = 1; i <= 10; ++i) { printf("%d: ", i); proper_divisors(i, true); }
int max = 0; int max_i = 1;
for (int i = 1; i <= 20000; ++i) { int v = proper_divisors(i, false); if (v >= max) { max = v; max_i = i; } }
printf("%d with %d divisors\n", max_i, max); return 0;
} </lang>
- Output:
1: 2: 1 3: 1 4: 1 2 5: 1 6: 1 2 3 7: 1 8: 1 2 4 9: 1 3 10: 1 2 5 18480 with 79 divisors
C#
<lang csharp>namespace RosettaCode.ProperDivisors {
using System; using System.Collections.Generic; using System.Linq;
internal static class Program { private static IEnumerable<int> ProperDivisors(int number) { return Enumerable.Range(1, number / 2) .Where(divisor => number % divisor == 0); }
private static void Main() { foreach (var number in Enumerable.Range(1, 10)) { Console.WriteLine("{0}: {{{1}}}", number, string.Join(", ", ProperDivisors(number))); }
var record = Enumerable.Range(1, 20000).Select(number => new { Number = number, Count = ProperDivisors(number).Count() }).OrderByDescending(currentRecord => currentRecord.Count).First(); Console.WriteLine("{0}: {1}", record.Number, record.Count); } }
}</lang>
- Output:
1: {} 2: {1} 3: {1} 4: {1, 2} 5: {1} 6: {1, 2, 3} 7: {1} 8: {1, 2, 4} 9: {1, 3} 10: {1, 2, 5} 15120: 79
C++
<lang cpp>#include <vector>
- include <iostream>
- include <algorithm>
std::vector<int> properDivisors ( int number ) {
std::vector<int> divisors ; for ( int i = 1 ; i < number / 2 + 1 ; i++ ) if ( number % i == 0 )
divisors.push_back( i ) ;
return divisors ;
}
int main( ) {
std::vector<int> divisors ; unsigned int maxdivisors = 0 ; int corresponding_number = 0 ; for ( int i = 1 ; i < 11 ; i++ ) { divisors = properDivisors ( i ) ; std::cout << "Proper divisors of " << i << ":\n" ; for ( int number : divisors ) {
std::cout << number << " " ;
} std::cout << std::endl ; divisors.clear( ) ; } for ( int i = 11 ; i < 20001 ; i++ ) { divisors = properDivisors ( i ) ; if ( divisors.size( ) > maxdivisors ) {
maxdivisors = divisors.size( ) ; corresponding_number = i ;
} divisors.clear( ) ; }
std::cout << "Most divisors has " << corresponding_number << " , it has " << maxdivisors << " divisors!\n" ; return 0 ;
} </lang>
- Output:
Proper divisors of 1: Proper divisors of 2: 1 Proper divisors of 3: 1 Proper divisors of 4: 1 2 Proper divisors of 5: 1 Proper divisors of 6: 1 2 3 Proper divisors of 7: 1 Proper divisors of 8: 1 2 4 Proper divisors of 9: 1 3 Proper divisors of 10: 1 2 5 Most divisors has 15120 , it has 79 divisors!
Ceylon
<lang ceylon>shared void properDivisors() {
function divisors(Integer int) => if(int <= 1) then {} else (1..int / 2).filter((Integer element) => element.divides(int));
for(i in 1..10) { print("``i`` => ``divisors(i)``"); }
value start = 1; value end = 20k; value mostDivisors = (start..end) // number -> divisors count: {1->0, 2->1, ... 6->3, ...} .map((Integer element) => element->divisors(element).size) // group based on the number of divisors .group((Integer->Integer element) => let(i->count = element) count) // clean it up a bit .mapItems((Integer key, [<Integer->Integer>+] item) => item*.key) // find the group with the most divisors .max((Integer->[Integer+] x, Integer->[Integer+] y) => x.key <=> y.key);
print("the number(s) with the most divisors between ``start`` and ``end`` is/are: ``mostDivisors?.item else "nothing"`` with ``mostDivisors?.key else "no"`` divisors"); }</lang>
- Output:
1 => [] 2 => { 1 } 3 => { 1 } 4 => { 1, 2 } 5 => { 1 } 6 => { 1, 2, 3 } 7 => { 1 } 8 => { 1, 2, 4 } 9 => { 1, 3 } 10 => { 1, 2, 5 } the number(s) with the most divisors between 1 and 20000 is/are: [15120, 18480] with 79 divisors
D
Currently the lambda of the filter allocates a closure on the GC-managed heap. <lang d>void main() /*@safe*/ {
import std.stdio, std.algorithm, std.range, std.typecons;
immutable properDivs = (in uint n) pure nothrow @safe /*@nogc*/ => iota(1, (n + 1) / 2 + 1).filter!(x => n % x == 0 && n != x);
iota(1, 11).map!properDivs.writeln; iota(1, 20_001).map!(n => tuple(properDivs(n).count, n)).reduce!max.writeln;
}</lang>
- Output:
[[], [1], [1], [1, 2], [1], [1, 2, 3], [1], [1, 2, 4], [1, 3], [1, 2, 5]] Tuple!(uint, int)(79, 18480)
The Run-time is about 0.67 seconds with the ldc2 compiler.
EchoLisp
<lang scheme> (lib 'list) ;; list-delete
- let n = product p_i^a_i , p_i prime
- number of divisors = product (a_i + 1) - 1
(define (numdivs n)
(1- (apply * (map (lambda(g) (1+ (length g))) (group (prime-factors n))))))
(remember 'numdivs)
- prime powers
- input
- a list g of grouped prime factors ( 3 3 3 ..)
- returns (1 3 9 27 ...)
(define (ppows g (mult 1)) (for/fold (ppows '(1)) ((a g)) (set! mult (* mult a)) (cons mult ppows)))
- proper divisors
- decomp n into ((2 2 ..) ( 3 3 ..) ) prime factors groups
- combines (1 2 4 8 ..) (1 3 9 ..) lists
- remove n from the list
(define (divs n)
(if (<= n 1) null (list-delete (for/fold (divs'(1)) ((g (map ppows (group (prime-factors n)))))
(for*/list ((a divs) (b g)) (* a b)))
n )))
- find number(s) with max # of proper divisors
- returns list of (n . maxdivs) for n in range 2..N
(define (most-proper N)
(define maxdivs 1) (define ndivs 0) (for/fold (most-proper null) ((n (in-range 2 N))) (set! ndivs (numdivs n)) #:continue (< ndivs maxdivs) (when (> ndivs maxdivs) (set!-values (most-proper maxdivs) (values null ndivs))) (cons (cons n maxdivs) most-proper)))
</lang>
- Output:
<lang scheme> (for ((i (in-range 1 11))) (writeln i (divs i))) 1 null 2 (1) 3 (1) 4 (2 1) 5 (1) 6 (2 3 1) 7 (1) 8 (4 2 1) 9 (3 1) 10 (2 5 1)
(most-proper 20000)
→ ((18480 . 79) (15120 . 79))
(most-proper 1_000_000)
→ ((997920 . 239) (982800 . 239) (942480 . 239) (831600 . 239) (720720 . 239))
(lib 'bigint) (numdivs 95952222101012742144) → 666 ;; 🎩 </lang>
Eiffel
<lang Eiffel> class APPLICATION
create make
feature
make -- Test the feature proper_divisors. local list: LINKED_LIST [INTEGER] count, number: INTEGER do across 1 |..| 10 as c loop list := proper_divisors (c.item) io.put_string (c.item.out + ": ") across list as l loop io.put_string (l.item.out + " ") end io.new_line end across 1 |..| 20000 as c loop list := proper_divisors (c.item) if list.count > count then count := list.count number := c.item end end io.put_string (number.out + " has with " + count.out + " divisors the highest number of proper divisors.") end
proper_divisors (n: INTEGER): LINKED_LIST [INTEGER] -- Proper divisors of 'n'. do create Result.make across 1 |..| (n - 1) as c loop if n \\ c.item = 0 then Result.extend (c.item) end end end
end </lang>
- Output:
1: 2: 1 3: 1 4: 1 2 5: 1 6: 1 2 3 7: 1 8: 1 2 4 9: 1 3 10: 1 2 5 15120 has with 79 divisors the highest number of proper divisors.
Elixir
<lang elixir>defmodule Proper do
def divisors(1), do: [] def divisors(n), do: [1 | divisors(2,n,:math.sqrt(n))] |> Enum.sort defp divisors(k,_n,q) when k>q, do: [] defp divisors(k,n,q) when rem(n,k)>0, do: divisors(k+1,n,q) defp divisors(k,n,q) when k * k == n, do: [k | divisors(k+1,n,q)] defp divisors(k,n,q) , do: [k,div(n,k) | divisors(k+1,n,q)] def most_divisors(limit) do {length,nums} = Enum.group_by(1..limit, fn n -> length(divisors(n)) end) |> Enum.max_by(fn {length,_nums} -> length end) IO.puts "With #{length}, Number #{inspect nums} has the most divisors" end
end
Enum.each(1..10, fn n ->
IO.puts "#{n}: #{inspect Proper.divisors(n)}"
end) Proper.most_divisors(20000)</lang>
- Output:
1: [] 2: [1] 3: [1] 4: [1, 2] 5: [1] 6: [1, 2, 3] 7: [1] 8: [1, 2, 4] 9: [1, 3] 10: [1, 2, 5] With 79, Number [18480, 15120] has the most divisors
Erlang
<lang erlang>-module(properdivs). -export([divs/1,sumdivs/1,longest/1]).
divs(0) -> []; divs(1) -> []; divs(N) -> lists:sort([1] ++ divisors(2,N,math:sqrt(N))).
divisors(K,_N,Q) when K > Q -> []; divisors(K,N,Q) when N rem K =/= 0 ->
divisors(K+1,N,Q);
divisors(K,N,Q) when K * K == N ->
[K] ++ divisors(K+1,N,Q);
divisors(K,N,Q) ->
[K, N div K] ++ divisors(K+1,N,Q).
sumdivs(N) -> lists:sum(divs(N)).
longest(Limit) -> longest(Limit,0,0,1).
longest(L,Current,CurLeng,Acc) when Acc >= L ->
io:format("With ~w, Number ~w has the most divisors~n", [CurLeng,Current]);
longest(L,Current,CurLeng,Acc) ->
A = length(divs(Acc)), if A > CurLeng -> longest(L,Acc,A,Acc+1); true -> longest(L,Current,CurLeng,Acc+1) end.</lang>
- Output:
1> [io:format("X: ~w, N: ~w~n", [N,properdivs:divs(N)]) || N <- lists:seq(1,10)]. X: 1, N: [] X: 2, N: [1] X: 3, N: [1] X: 4, N: [1,2] X: 5, N: [1] X: 6, N: [1,2,3] X: 7, N: [1] X: 8, N: [1,2,4] X: 9, N: [1,3] X: 10, N: [1,2,5] [ok,ok,ok,ok,ok,ok,ok,ok,ok,ok] 2> properdivs:longest(20000). With 79, Number 15120 has the most divisors
Fortran
Compiled using G95 compiler, run on x86 system under Puppy Linux <lang Fortran>
function icntprop(num ) icnt=0 do i=1 , num-1 if (mod(num , i) .eq. 0) then icnt = icnt + 1 if (num .lt. 11) print *,' ',i end if end do icntprop = icnt end function limit = 20000 maxcnt = 0 print *,'N divisors' do j=1,limit,1 if (j .lt. 11) print *,j icnt = icntprop(j) if (icnt .gt. maxcnt) then maxcnt = icnt maxj = j end if end do print *,' ' print *,' from 1 to ',limit print *,maxj,' has max proper divisors: ',maxcnt end
</lang>
- Output:
N divisors 1 2 1 3 1 4 1 2 5 1 6 1 2 3 7 1 8 1 2 4 9 1 3 10 1 2 5 from 1 to 20000 15120 has max proper divisors: 79
Haskell
<lang Haskell>import Data.Ord import Data.List
divisors :: (Integral a) => a -> [a] divisors n = filter ((0 ==) . (n `mod`)) [1 .. (n `div` 2)]
main :: IO () main = do
putStrLn "divisors of 1 to 10:" mapM_ (print . divisors) [1 .. 10] putStrLn "a number with the most divisors within 1 to 20000 (number, count):" print $ maximumBy (comparing snd) [(n, length $ divisors n) | n <- [1 .. 20000]]</lang>
- Output:
divisors of 1 to 10: [] [1] [1] [1,2] [1] [1,2,3] [1] [1,2,4] [1,3] [1,2,5] a number with the most divisors within 1 to 20000 (number, count): (18480,79)
J
The proper divisors of an integer are the Factors of an integer without the integer itself.
So, borrowing from the J implementation of that related task:
<lang J>factors=: [: /:~@, */&>@{@((^ i.@>:)&.>/)@q:~&__ properDivisors=: factors -. ]</lang>
Proper divisors of numbers 1 through 10:
<lang J> (,&": ' -- ' ,&": properDivisors)&>1+i.10 1 -- 2 -- 1 3 -- 1 4 -- 1 2 5 -- 1 6 -- 1 2 3 7 -- 1 8 -- 1 2 4 9 -- 1 3 10 -- 1 2 5</lang>
Number(s) not exceeding 20000 with largest number of proper divisors (and the count of those divisors):
<lang J> (, #@properDivisors)&> 1+I.(= >./) #@properDivisors@> 1+i.20000 15120 79 18480 79</lang>
Note that it's a bit more efficient to simply count factors here, when selecting the candidate numbers.
<lang J> (, #@properDivisors)&> 1+I.(= >./) #@factors@> 1+i.20000 15120 79 18480 79</lang>
We could also arbitrarily toss either 15120 or 18480 (keeping the other number), if it were important that we produce only one result.
Java
<lang java5>import java.util.Collections; import java.util.LinkedList; import java.util.List;
public class Proper{
public static List<Integer> properDivs(int n){ List<Integer> divs = new LinkedList<Integer>(); if(n == 1) return divs; divs.add(1); for(int x = 2; x < n; x++){ if(n % x == 0) divs.add(x); } Collections.sort(divs); return divs; } public static void main(String[] args){ for(int x = 1; x <= 10; x++){ System.out.println(x + ": " + properDivs(x)); } int x = 0, count = 0; for(int n = 1; n <= 20000; n++){ if(properDivs(n).size() > count){ x = n; count = properDivs(n).size(); } } System.out.println(x + ": " + count); }
}</lang>
- Output:
1: [] 2: [1] 3: [1] 4: [1, 2] 5: [1] 6: [1, 2, 3] 7: [1] 8: [1, 2, 4] 9: [1, 3] 10: [1, 2, 5] 15120: 79
JavaScript
<lang JavaScript>(function () {
// Proper divisors function properDivisors(n) { if (n < 2) return []; else { var rRoot = Math.sqrt(n), intRoot = Math.floor(rRoot),
lows = range(1, intRoot).filter(function (x) { return (n % x) === 0; });
return lows.concat(lows.slice(1).map(function (x) { return n / x; }).reverse().slice((rRoot === intRoot) | 0)); } }
// [m..n] function range(m, n) { var a = Array(n - m + 1), i = n + 1; while (i--) a[i - 1] = i; return a; }
var tblOneToTen = [ ['Number', 'Proper Divisors', 'Count'] ].concat(range(1, 10).map(function (x) { var ds = properDivisors(x);
return [x, ds.join(', '), ds.length]; })),
dctMostBelow20k = range(1, 20000).reduce(function (a, x) { var lng = properDivisors(x).length;
return lng > a.divisorCount ? { n: x, divisorCount: lng } : a; }, { n: 0, divisorCount: 0 });
// a -> bool -> s -> s function wikiTable(lstRows, blnHeaderRow, strStyle) { return '{| class="wikitable" ' + ( strStyle ? 'style="' + strStyle + '"' : ) + lstRows.map(function (lstRow, iRow) { var strDelim = ((blnHeaderRow && !iRow) ? '!' : '|');
return '\n|-\n' + strDelim + ' ' + lstRow.map(function (v) { return typeof v === 'undefined' ? ' ' : v; }).join(' ' + strDelim + strDelim + ' '); }).join() + '\n|}'; }
return wikiTable( tblOneToTen, true ) + '\n\nMost proper divisors below 20,000:\n\n ' + JSON.stringify( dctMostBelow20k );
})();</lang>
- Output:
Number | Proper Divisors | Count |
---|---|---|
1 | 0 | |
2 | 1 | 1 |
3 | 1 | 1 |
4 | 1, 2 | 2 |
5 | 1 | 1 |
6 | 1, 2, 3 | 3 |
7 | 1 | 1 |
8 | 1, 2, 4 | 3 |
9 | 1, 3 | 2 |
10 | 1, 2, 5 | 3 |
Most proper divisors below 20,000:
{"n":15120,"divisorCount":79}
jq
In the following, proper_divisors returns a stream. In order to count the number of items in the stream economically, we first define "count(stream)": <lang jq>def count(stream): reduce stream as $i (0; . + 1);
- unordered
def proper_divisors:
. as $n | if $n > 1 then 1, ( range(2; 1 + (sqrt|floor)) as $i | if ($n % $i) == 0 then $i, (($n / $i) | if . == $i then empty else . end) else empty
end)
else empty end;
- The first integer in 1 .. n inclusive
- with the maximal number of proper divisors in that range:
def most_proper_divisors(n):
reduce range(1; n+1) as $i ( [null, 0]; count( $i | proper_divisors ) as $count | if $count > .[1] then [$i, $count] else . end);</lang>
The tasks: <lang jq>"The proper divisors of the numbers 1 to 10 inclusive are:", (range(1;11) as $i | "\($i): \( [ $i | proper_divisors] )"), "", "The pair consisting of the least number in the range 1 to 20,000 with", "the maximal number proper divisors together with the corresponding", "count of proper divisors is:", most_proper_divisors(20000) </lang>
- Output:
<lang sh>$ jq -n -c -r -f /Users/peter/jq/proper_divisors.jq The proper divisors of the numbers 1 to 10 inclusive are: 1: [] 2: [1] 3: [1] 4: [1,2] 5: [1] 6: [1,2,3] 7: [1] 8: [1,2,4] 9: [1,3] 10: [1,2,5]
The pair consisting of the least number in the range 1 to 20,000 with the maximal number proper divisors together with the corresponding count of proper divisors is: [15120,79]</lang>
Julia
Use factor
to obtain the prime factorization of the target number. I adopted the argument handling style of factor
in my properdivisors
function.
<lang Julia>
function properdivisors{T<:Integer}(n::T)
0 < n || throw(ArgumentError("number to be factored must be ≥ 0, got $n")) 1 < n || return T[] !isprime(n) || return T[one(T), n] f = factor(n) d = T[one(T)] for (k, v) in f c = T[k^i for i in 0:v] d = d*c' d = reshape(d, length(d)) end sort!(d) return d[1:end-1]
end
lo = 1 hi = 10 println("List the proper divisors for ", lo, " through ", hi, ".") for i in lo:hi
println(@sprintf("%4d", i), " ", properdivisors(i))
end
hi = 2*10^4 println("\nFind the numbers within [", lo, ",", hi, "] having the most divisors.")
maxdiv = 0 nlst = Int[]
for i in lo:hi
ndiv = length(properdivisors(i)) if ndiv > maxdiv maxdiv = ndiv nlst = [i] elseif ndiv == maxdiv push!(nlst, i) end
end
println(nlst, " have the maximum proper divisor count of ", maxdiv, ".") </lang>
- Output:
List the proper divisors for 1 through 10. 1 [] 2 [1,2] 3 [1,3] 4 [1,2] 5 [1,5] 6 [1,2,3] 7 [1,7] 8 [1,2,4] 9 [1,3] 10 [1,2,5] Find the numbers within [1,20000] having the most divisors. [15120,18480] have the maximum proper divisor count of 79.
Mathematica / Wolfram Language
A Function that yields the proper divisors of an integer n: <lang Mathematica>ProperDivisors[n_Integer /; n > 0] := Most@Divisors@n;</lang>
Proper divisors of n from 1 to 10: <lang Mathematica>Grid@Table[{n, ProperDivisors[n]}, {n, 1, 10}]</lang>
- Output:
1 {} 2 {1} 3 {1} 4 {1,2} 5 {1} 6 {1,2,3} 7 {1} 8 {1,2,4} 9 {1,3} 10 {1,2,5}
The number with the most divisors between 1 and 20,000: <lang Mathematica>Fold[
Last[SortBy[{#1, {#2, Length@ProperDivisors[#2]}}, Last]] &, {0, 0}, Range[20000]]</lang>
- Output:
{18480, 79}
An alternate way to find the number with the most divisors between 1 and 20,000: <lang Mathematica>Last@SortBy[
Table[ {n, Length@ProperDivisors[n]}, {n, 1, 20000}], Last]</lang>
- Output:
{15120, 79}
Oberon-2
<lang oberon2> MODULE ProperDivisors; IMPORT
Out;
CONST
initialSize = 128;
TYPE
Result* = POINTER TO ResultDesc; ResultDesc = RECORD found-: LONGINT; (* number of slots in pd *) pd-: POINTER TO ARRAY OF LONGINT; cap: LONGINT; (* Capacity *) END;
VAR
i,found,max,idxMx: LONGINT; mx: ARRAY 32 OF LONGINT; rs: Result;
PROCEDURE (r: Result) Init(size: LONGINT); BEGIN r.found := 0; r.cap := size; NEW(r.pd,r.cap); END Init;
PROCEDURE (r: Result) Add(n: LONGINT); BEGIN (* Out.String("--->");Out.LongInt(n,0);Out.String(" At: ");Out.LongInt(r.found,0);Out.Ln; *) IF (r.found < LEN(r.pd^) - 1) THEN r.pd[r.found] := n; ELSE (* expand pd for more room *) END; INC(r.found); END Add;
PROCEDURE (r:Result) Show(); VAR i: LONGINT; BEGIN Out.String("(Result:");Out.LongInt(r.found + 1,0);(* Out.String("/");Out.LongInt(r.cap,0);*) Out.String("-"); IF r.found > 0 THEN FOR i:= 0 TO r.found - 1 DO Out.LongInt(r.pd[i],0); IF i = r.found - 1 THEN Out.Char(')') ELSE Out.Char(',') END END END; Out.Ln END Show;
PROCEDURE (r:Result) Reset(); BEGIN r.found := 0; END Reset;
PROCEDURE GetFor(n: LONGINT;VAR rs: Result); VAR i: LONGINT; BEGIN IF n > 1 THEN rs.Add(1);i := 2; WHILE (i < n) DO IF (n MOD i) = 0 THEN rs.Add(i) END; INC(i) END END; END GetFor;
BEGIN
NEW(rs);rs.Init(initialSize); FOR i := 1 TO 10 DO Out.LongInt(i,4);Out.Char(':'); GetFor(i,rs); rs.Show(); rs.Reset(); END; Out.LongInt(100,4);Out.Char(':');GetFor(100,rs);rs.Show();rs.Reset(); max := 0;idxMx := 0;found := 0; FOR i := 1 TO 20000 DO GetFor(i,rs); IF rs.found > max THEN idxMx:= 0;mx[idxMx] := i;max := rs.found ELSIF rs.found = max THEN INC(idxMx);mx[idxMx] := i END; rs.Reset() END; Out.String("Found: ");Out.LongInt(idxMx + 1,0); Out.String(" Numbers with most proper divisors "); Out.LongInt(max,0);Out.String(": ");Out.Ln; FOR i := 0 TO idxMx DO Out.LongInt(mx[i],0);Out.Ln END
END ProperDivisors. </lang>
- Output:
1:(Result:1- 2:(Result:2-1) 3:(Result:2-1) 4:(Result:3-1,2) 5:(Result:2-1) 6:(Result:4-1,2,3) 7:(Result:2-1) 8:(Result:4-1,2,4) 9:(Result:3-1,3) 10:(Result:4-1,2,5) 100:(Result:9-1,2,4,5,10,20,25,50) Found: 2 Numbers with most proper divisors 79: 15120 18480
Oforth
<lang Oforth>Integer method: properDivs { seq(self 2 / ) filter(#[ self swap mod 0 == ]) }
10 seq apply(#[ dup print " : " print properDivs println ]) 20000 seq map(#[ dup properDivs size Pair new ]) reduce(#maxKey) println</lang>
- Output:
1 : [] 2 : [1] 3 : [1] 4 : [1, 2] 5 : [1] 6 : [1, 2, 3] 7 : [1] 8 : [1, 2, 4] 9 : [1, 3] 10 : [1, 2, 5] [79, 15120]
PARI/GP
<lang parigp>proper(n)=if(n==1, [], my(d=divisors(n)); d[2..#d]); apply(proper, [1..10]) r=at=0; for(n=1,20000, t=numdiv(n); if(t>r, r=t; at=n)); [at, numdiv(t)-1]</lang>
- Output:
%1 = [[], [2], [3], [2, 4], [5], [2, 3, 6], [7], [2, 4, 8], [3, 9], [2, 5, 10]] %2 = [15120, 7]
Perl
Using a module for divisors
<lang perl>use ntheory qw/divisors/; sub proper_divisors {
my $n = shift; # Like Pari/GP, divisors(0) = (0,1) and divisors(1) = () return 1 if $n == 0; my @d = divisors($n); pop @d; # divisors are in sorted order, so last entry is the input @d;
} say "$_: ", join " ", proper_divisors($_) for 1..10;
- 1. For the max, we can do a traditional loop.
my($max,$ind) = (0,0); for (1..20000) {
my $nd = scalar proper_divisors($_); ($max,$ind) = ($nd,$_) if $nd > $max;
} say "$max $ind";
- 2. Or we can use List::Util's max with decoration (this exploits its implementation)
{
use List::Util qw/max/; no warnings 'numeric'; say max(map { scalar(proper_divisors($_)) . " $_" } 1..20000);
}</lang>
- Output:
1: 2: 1 3: 1 4: 1 2 5: 1 6: 1 2 3 7: 1 8: 1 2 4 9: 1 3 10: 1 2 5 79 15120 79 18480
Note that the first code will choose the first max, while the second chooses the last.
Perl 6
<lang perl6>sub propdiv (\x) {
my @l =(1 if x > 1), gather for 2 .. x.sqrt.floor -> \d { my \y = x div d; if y * d == x { take d; take y unless y == d } } gather @l.deepmap(*.take);
}
say "$_ ", propdiv($_) for 1..10;
my $max = 0; my @candidates; for 1..20000 {
my @pd = propdiv($_); my $pd = @pd.elems; if $pd > $max { @candidates = (); $max = $pd; } push @candidates, $_ if $pd == $max;
} say "max = $max, candidates = @candidates[]";</lang>
- Output:
1 Nil 2 1 3 1 4 1 2 5 1 6 1 2 3 7 1 8 1 2 4 9 1 3 10 1 2 5 max = 79, candidates = 15120 18480
Phix
The factors routine is an auto-include. The actual implementation of it, from builtins\pfactors.e is <lang Phix>global function factors(atom n, integer include1=0) -- returns a list of all integer factors of n -- if include1 is 0 (the default), result does not contain either 1 or n -- if include1 is 1, and n>1, the result contains 1 and n -- if include1 is -1, and n>1, the result contains 1 but not n sequence lfactors = {}, hfactors = {} atom hfactor integer p = 2,
lim = floor(sqrt(n))
if n!=1 and include1!=0 then lfactors = {1} if include1=1 then hfactors = {n} end if end if while p<=lim do if remainder(n,p)=0 then lfactors = append(lfactors,p) hfactor = n/p if hfactor=p then exit end if hfactors = prepend(hfactors,hfactor) end if p += 1 end while return lfactors & hfactors
end function</lang> The compiler knows where to find that, so the main program is just: <lang Phix>for i=1 to 10 do
?{i,factors(i,-1)}
end for
integer maxd = 0, k sequence candidates = {}
for i=1 to 20000 do k = length(factors(i,-1)) if k>=maxd then if k=maxd then candidates &= i else candidates = {i} maxd = k end if end if end for printf(1,"%d divisors:", maxd) ?candidates {} = wait_key()</lang>
- Output:
{1,{}} {2,{1}} {3,{1}} {4,{1,2}} {5,{1}} {6,{1,2,3}} {7,{1}} {8,{1,2,4}} {9,{1,3}} {10,{1,2,5}} 79 divisors:{15120,18480}
PicoLisp
<lang PicoLisp># Generate all proper divisors. (de propdiv (N)
(head -1 (filter '((X) (=0 (% N X))) (range 1 N) )) )
- Obtaining the values from 1 to 10 inclusive.
(mapcar propdiv (range 1 10))
- Output:
- (NIL (1) (1) (1 2) (1) (1 2 3) (1) (1 2 4) (1 3) (1 2 5))</lang>
Brute-force
<lang PicoLisp>(de propdiv (N)
(cdr (rot (make (for I N (and (=0 (% N I)) (link I)) ) ) ) ) )
(de countdiv (N)
(let C -1 (for I N (and (=0 (% N I)) (inc 'C)) ) C ) )
(let F (-5 -8)
(tab F "N" "LIST") (for I 10 (tab F I (glue " + " (propdiv I)) ) ) )
(println
(maxi countdiv (range 1 20000) ) )</lang>
Factorization
<lang PicoLisp>(de accu1 (Var Key)
(if (assoc Key (val Var)) (con @ (inc (cdr @))) (push Var (cons Key 2)) ) Key )
(de factor (N)
(let (R NIL D 2 L (1 2 2 . (4 2 4 2 4 6 2 6 .)) M (sqrt N) ) (while (>= M D) (if (=0 (% N D)) (setq M (sqrt (setq N (/ N (accu1 'R D)))) ) (inc 'D (pop 'L)) ) ) (accu1 'R N) (dec (apply * (mapcar cdr R))) ) )
(bench
(println (maxi factor (range 1 20000) ) @@ ) )</lang>
Output:
15120 79 0.081 sec
PL/I
<lang pli>*process source xref;
(subrg): cpd: Proc Options(main); p9a=time(); Dcl (p9a,p9b) Pic'(9)9'; Dcl cnt(3) Bin Fixed(31) Init((3)0); Dcl x Bin Fixed(31); Dcl pd(300) Bin Fixed(31); Dcl sumpd Bin Fixed(31); Dcl npd Bin Fixed(31); Dcl hi Bin Fixed(31) Init(0); Dcl (xl(10),xi) Bin Fixed(31); Dcl i Bin Fixed(31); Do x=1 To 10; Call proper_divisors(x,pd,npd); Put Edit(x,' -> ',(pd(i) Do i=1 To npd))(Skip,f(2),a,10(f(2))); End; xi=0; Do x=1 To 20000; Call proper_divisors(x,pd,npd); Select; When(npd>hi) Do; xi=1; xl(1)=x; hi=npd; End; When(npd=hi) Do; xi+=1; xl(xi)=x; End; Otherwise; End; End; Put Edit(hi,' -> ',(xl(i) Do i=1 To xi))(Skip,f(3),a,10(f(6)));
x= 166320; Call proper_divisors(x,pd,npd); Put Edit(x,' -> ',npd)(Skip,f(8),a,f(4)); x=1441440; Call proper_divisors(x,pd,npd); Put Edit(x,' -> ',npd)(Skip,f(8),a,f(4));
p9b=time(); Put Edit((p9b-p9a)/1000,' seconds elapsed')(Skip,f(6,3),a); Return;
proper_divisors: Proc(n,pd,npd); Dcl (n,pd(300),npd) Bin Fixed(31); Dcl (d,delta) Bin Fixed(31); npd=0; If n>1 Then Do; If mod(n,2)=1 Then /* odd number */ delta=2; Else /* even number */ delta=1; Do d=1 To n/2 By delta; If mod(n,d)=0 Then Do; npd+=1; pd(npd)=d; End; End; End; End;
End;</lang>
- Output:
1 -> 2 -> 1 3 -> 1 4 -> 1 2 5 -> 1 6 -> 1 2 3 7 -> 1 8 -> 1 2 4 9 -> 1 3 10 -> 1 2 5 79 -> 15120 18480 166320 -> 159 1441440 -> 287 0.530 seconds elapsed
PowerShell
version 1
<lang PowerShell> function proper-divisor ($n) {
if($n -ge 2) { $lim = [Math]::Floor([Math]::Sqrt($n)) $less, $greater = @(1), @() for($i = 2; $i -lt $lim; $i++){ if($n%$i -eq 0) { $less += @($i) $greater = @($n/$i) + $greater } } if(($lim -ne 1) -and ($n%$lim -eq 0)) {$less += @($lim)} $($less + $greater) } else {@()}
} "$(proper-divisor 100)" "$(proper-divisor 496)" "$(proper-divisor 2048)" </lang>
version 2
<lang PowerShell> function proper-divisor ($n) {
if($n -ge 2) { $lim = [Math]::Floor($n/2)+1 $proper = @(1) for($i = 2; $i -lt $lim; $i++){ if($n%$i -eq 0) { $proper += @($i) } } $proper } else {@()}
} "$(proper-divisor 100)" "$(proper-divisor 496)" "$(proper-divisor 2048)" </lang>
version 3
<lang PowerShell> function eratosthenes ($n) {
if($n -gt 1){ $prime = @(0..$n| foreach{$true}) $m = [Math]::Floor([Math]::Sqrt($n)) function multiple($i) { for($j = $i*$i; $j -le $n; $j += $i) { $prime[$j] = $false } } multiple 2 for($i = 3; $i -le $m; $i += 2) { if($prime[$i]) {multiple $i} } 2 for($i = 3; $i -le $n; $i += 2) { if($prime[$i]) {$i} } } else { Write-Error "$n is not greater than 1" }
} function prime-decomposition ($n) {
$array = eratosthenes $n $prime = @() foreach($p in $array) { while($n%$p -eq 0) { $n /= $p $prime += @($p) } } $prime
} function proper-divisor ($n) {
if($n -ge 2) { $array = prime-decomposition $n $lim = $array.Count function state($res, $i){ if($i -lt $lim) { state ($res) ($i + 1) state ($res*$array[$i]) ($i + 1) } elseif($res -lt $n) {$res} } state 1 0 | sort -Unique } else {@()}
} "$(proper-divisor 100)" "$(proper-divisor 496)" "$(proper-divisor 2048)" </lang> Output:
1 2 4 5 10 20 25 50 1 2 4 8 16 31 62 124 248 1 2 4 8 16 32 64 128 256 512 1024
Prolog
Taking a cue from an SO answer:
<lang prolog>divisor(N, Divisor) :-
UpperBound is round(sqrt(N)), between(1, UpperBound, D), 0 is N mod D, ( Divisor = D ; LargerDivisor is N/D, LargerDivisor =\= D, Divisor = LargerDivisor ).
proper_divisor(N, D) :-
divisor(N, D), D =\= N.
%% Task 1
%
proper_divisors(N, Ds) :-
setof(D, proper_divisor(N, D), Ds).
%% Task 2
%
show_proper_divisors_of_range(Low, High) :-
findall( N:Ds, ( between(Low, High, N), proper_divisors(N, Ds) ), Results ), maplist(writeln, Results).
%% Task 3
%
proper_divisor_count(N, Count) :-
proper_divisors(N, Ds), length(Ds, Count).
find_most_proper_divisors_in_range(Low, High, Result) :-
aggregate_all( max(Count, N), ( between(Low, High, N), proper_divisor_count(N, Count) ), max(MaxCount, Num) ), Result = (num(Num)-divisor_count(MaxCount)).</lang>
Output:
<lang prolog>?- show_proper_divisors_of_range(1,10). 2:[1] 3:[1] 4:[1,2] 5:[1] 6:[1,2,3] 7:[1] 8:[1,2,4] 9:[1,3] 10:[1,2,5] true.
?- find_most_proper_divisors_in_range(1,20000,Result). Result = num(15120)-divisor_count(79). </lang>
Python
Python: Literal
A very literal interpretation <lang python>>>> def proper_divs2(n): ... return {x for x in range(1, (n + 1) // 2 + 1) if n % x == 0 and n != x} ... >>> [proper_divs2(n) for n in range(1, 11)] [set(), {1}, {1}, {1, 2}, {1}, {1, 2, 3}, {1}, {1, 2, 4}, {1, 3}, {1, 2, 5}] >>> >>> n, length = max(((n, len(proper_divs2(n))) for n in range(1, 20001)), key=lambda pd: pd[1]) >>> n 15120 >>> length 79 >>> </lang>
Python: From prime factors
I found a reference on how to generate factors from all the prime factors and the number of times each prime factor goes into N - its multiplicity.
For example, given N having prime factors P(i) with associated multiplicity M(i}) then the factors are given by:
for m[0] in range(M(0) + 1): for m[1] in range(M[1] + 1): ... for m[i - 1] in range(M[i - 1] + 1): mult = 1 for j in range(i): mult *= P[j] ** m[j] yield mult
This version is over an order of magnitude faster for generating the proper divisors of the first 20,000 integers; at the expense of simplicity. <lang python>from math import sqrt from functools import lru_cache, reduce from collections import Counter from itertools import product
MUL = int.__mul__
def prime_factors(n):
'Map prime factors to their multiplicity for n' d = _divs(n) d = [] if d == [n] else (d[:-1] if d[-1] == d else d) pf = Counter(d) return dict(pf)
@lru_cache(maxsize=None) def _divs(n):
'Memoized recursive function returning prime factors of n as a list' for i in range(2, int(sqrt(n)+1)): d, m = divmod(n, i) if not m: return [i] + _divs(d) return [n]
def proper_divs(n):
Return the set of proper divisors of n. pf = prime_factors(n) pfactors, occurrences = pf.keys(), pf.values() multiplicities = product(*(range(oc + 1) for oc in occurrences)) divs = {reduce(MUL, (pf**m for pf, m in zip(pfactors, multis)), 1) for multis in multiplicities} try: divs.remove(n) except KeyError: pass return divs or ({1} if n != 1 else set())
if __name__ == '__main__':
rangemax = 20000 print([proper_divs(n) for n in range(1, 11)]) print(*max(((n, len(proper_divs(n))) for n in range(1, 20001)), key=lambda pd: pd[1]))</lang>
- Output:
[set(), {1}, {1}, {1, 2}, {1}, {1, 2, 3}, {1}, {1, 2, 4}, {1, 3}, {1, 2, 5}] 15120 79
Racket
Short version
<lang racket>#lang racket (require math) (define (proper-divisors n) (drop-right (divisors n) 1)) (for ([n (in-range 1 (add1 10))])
(printf "proper divisors of: ~a\t~a\n" n (proper-divisors n)))
(define most-under-20000
(for/fold ([best '(1)]) ([n (in-range 2 (add1 20000))]) (define divs (proper-divisors n)) (if (< (length (cdr best)) (length divs)) (cons n divs) best)))
(printf "~a has ~a proper divisors\n"
(car most-under-20000) (length (cdr most-under-20000)))</lang>
- Output:
proper divisors of: 1 () proper divisors of: 2 (1) proper divisors of: 3 (1) proper divisors of: 4 (1 2) proper divisors of: 5 (1) proper divisors of: 6 (1 2 3) proper divisors of: 7 (1) proper divisors of: 8 (1 2 4) proper divisors of: 9 (1 3) proper divisors of: 10 (1 2 5) 15120 has 79 proper divisors
Long version
The main module will only be executed when this file is executed. When used as a library, it will not be used. <lang racket>#lang racket/base (provide fold-divisors ; name as per "Abundant..."
proper-divisors)
(define (fold-divisors v n k0 kons)
(define n1 (add1 n)) (cond [(>= n1 (vector-length v)) (define rv (make-vector n1 k0)) (for* ([n (in-range 1 n1)] [m (in-range (* 2 n) n1 n)]) (vector-set! rv m (kons n (vector-ref rv m)))) rv] [else v]))
(define proper-divisors
(let ([p.d-v (vector)]) (λ (n) (set! p.d-v (reverse (fold-divisors p.d-v n null cons))) (vector-ref p.d-v n))))
(module+ main
(for ([n (in-range 1 (add1 10))]) (printf "proper divisors of: ~a\t~a\n" n (proper-divisors n)))
(define count-proper-divisors (let ([p.d-v (vector)]) (λ(n) (set! p.d-v (fold-divisors p.d-v n 0 (λ (d n) (add1 n)))) (vector-ref p.d-v n))))
(void (count-proper-divisors 20000))
(define-values [C I] (for*/fold ([C 0] [I 1]) ([i (in-range 1 (add1 20000))] [c (in-value (count-proper-divisors i))] #:when [> c C]) (values c i))) (printf "~a has ~a proper divisors\n" I C))</lang>
The output is the same as the short version above.
REXX
version 1
<lang rexx>Call time 'R' Do x=1 To 10
Say x '->' proper_divisors(x) End
hi=1 Do x=1 To 20000
/* If x//1000=0 Then Say x */ npd=count_proper_divisors(x) Select When npd>hi Then Do list.npd=x hi=npd End When npd=hi Then list.hi=list.hi x Otherwise Nop End End
Say hi '->' list.hi
Say ' 166320 ->' count_proper_divisors(166320) Say '1441440 ->' count_proper_divisors(1441440)
Say time('E') 'seconds elapsed' Exit
proper_divisors: Procedure Parse Arg n If n=1 Then Return pd= /* Optimization reduces 37 seconds to 28 seconds */ If n//2=1 Then /* odd number */
delta=2
Else /* even number */
delta=1
Do d=1 To n%2 By delta
If n//d=0 Then pd=pd d End
Return space(pd)
count_proper_divisors: Procedure Parse Arg n Return words(proper_divisors(n))</lang>
- Output:
1 -> 2 -> 1 3 -> 1 4 -> 1 2 5 -> 1 6 -> 1 2 3 7 -> 1 8 -> 1 2 4 9 -> 1 3 10 -> 1 2 5 79 -> 15120 18480 166320 -> 159 1441440 -> 287 28.342000 seconds elapsed
version 2
The following REXX version is an adaptation of the optimized version for the REXX language example for Factors of an integer.
This REXX version handles all integers (negative, zero, positive) and automatically adjusts the precision (digits).
It also allows the specification of the ranges (for display and for finding the maximum), and allows for extra numbers.
With the (subroutine) optimization, it's over twenty times faster. <lang rexx>/*REXX program finds proper divisors (& count) of integer ranges; & max count.*/ parse arg bot top inc range xtra /*get optional arguments from CL.*/ top=word(top bot 10,1); bot=word(bot 1,1); inc=word(inc 1,1) /*1st range.*/ if range== then range=top /*use TOP for the 2nd range. */ w=length(top)+1; numeric digits max(9,w) /*'nuff digits for // operation*/ m=0
do n=bot to top by inc; q=Pdivs(n); #=words(q); if q=='∞' then #=q say right(n,max(20,digits())) 'has' center(#,4) "proper divisors: " q end /*n*/ /* [↑] process 1st range of integers.*/
say; @.='and'
do r=1 for range; q=Pdivs(r); #=words(q); if #<m then iterate @.#=@.# @. r; m=# end /*r*/ /* [↑] process 2nd range of integers.*/ __='is the highest number of proper divisors in range 1──►'range
say m __", and it's for: " subword(@.m,3) say /* [↓] handle any given extra numbers.*/
do i=1 for words(xtra); n=word(xtra,i) numeric digits max(9,length(n)+1); q=Pdivs(n); #=words(q) say right(n,max(20,w)) 'has' center(#,4) "proper divisors." end /*i*/ /* [↑] support extra specified integers*/
exit /*stick a fork in it, we're all done. */ /*────────────────────────────────────────────────────────────────────────────*/ Pdivs: procedure; parse arg x,b; x=abs(x); if x==1 then return odd=x//2; if x==0 then return '∞' a=1 /* [↓] use all or only odd #s. ___ */
do j=2+odd by 1+odd while j*j<x /*divide by some integers up to √ X */ if x//j==0 then do; a=a j; b=x%j b; end /*if ÷, add both divisors to α&ß*/ end /*j*/ /* [↑] % is the REXX integer division*/ /* [↓] adjust for a square. ___ */
if j*j==x then return a j b /*Was X a square? If so, add √ X */
return a b /*return the divisors (both lists). */</lang>
output when using the following input: 0 10 1 20000 166320 1441440 11796480000
0 has ∞ proper divisors: ∞ 1 has 0 proper divisors: 2 has 1 proper divisors: 1 3 has 1 proper divisors: 1 4 has 2 proper divisors: 1 2 5 has 1 proper divisors: 1 6 has 3 proper divisors: 1 2 3 7 has 1 proper divisors: 1 8 has 3 proper divisors: 1 2 4 9 has 2 proper divisors: 1 3 10 has 3 proper divisors: 1 2 5 79 is the highest number of proper divisors in range 1──►20000, and it's for: 15120 and 18480 166320 has 159 proper divisors. 1441440 has 287 proper divisors. 11796480000 has 329 proper divisors.
version 3
When factoring 20,000 integers, this REXX version is over 12% faster than the REXX version 2.
When factoring 200,000 integers, this REXX version is over 25% faster.
It accomplishes a faster speed by incorporating the calculation of an integer square root of an integer (without using any floating point arithmetic). <lang rexx>/*REXX program finds proper divisors (& count) of integer ranges; & max count.*/ parse arg bot top inc range xtra /*get optional arguments from CL.*/ top=word(top bot 10,1); bot=word(bot 1,1); inc=word(inc 1,1) /*1st range.*/ if range== then range=top /*use TOP for the 2nd range. */ w=length(top)+1; numeric digits max(9,w) /*'nuff digits for // operation*/ m=0
do n=bot to top by inc; q=Pdivs(n); #=words(q); if q=='∞' then #=q say right(n,max(20,digits())) 'has' center(#,4) "proper divisors: " q end /*n*/ /* [↑] process 1st range of integers.*/
say; @.='and'
do r=1 for range; q=Pdivs(r); #=words(q); if #<m then iterate @.#=@.# @. r; m=# end /*r*/ /* [↑] process 2nd range of integers.*/ __='is the highest number of proper divisors in range 1──►'range
say m __", and it's for: " subword(@.m,3) say /* [↓] handle any given extra numbers.*/
do i=1 for words(xtra); n=word(xtra,i) numeric digits max(9,length(n)+1); q=Pdivs(n); #=words(q) say right(n,max(20,w)) 'has' center(#,4) "proper divisors." end /*i*/ /* [↑] support extra specified integers*/
exit /*stick a fork in it, we're all done. */ /*────────────────────────────────────────────────────────────────────────────*/ Pdivs: procedure; parse arg x,b; x=abs(x); if x==1 then return odd=x//2; if x==0 then return '∞' /* ___ */ z=x; r=0; q=1; do while q<=z; q=q*4; end /*R will be the integer √ X */
do while q>1; q=q%4; _=z-r-q; r=r%2; if _>=0 then do; z=_; r=r+q; end; end
a=1 /* [↓] use all or only odd #s. ___ */
do j=2+odd by 1+odd to r-(r*r==x) /*divide by some integers up to √ X */ if x//j==0 then do; a=a j; b=x%j b; end /*if ÷, add both divisors to α&ß*/ end /*j*/ /* [↑] % is the REXX integer division*/ /* [↓] adjust for a square. ___ */
if j*j==x then return a j b /*Was X a square? If so, add √ X */
return a b /*return the divisors (both lists). */</lang>
output is identical to the 2nd REXX version.
Ruby
<lang ruby>require "prime"
class Integer
def proper_divisors return [] if self == 1 primes = prime_division.flat_map{|prime, freq| [prime] * freq} (1...primes.size).each_with_object([1]) do |n, res| primes.combination(n).map{|combi| res << combi.inject(:*)} end.flatten.uniq end
end
(1..10).map{|n| puts "#{n}: #{n.proper_divisors}"}
size, select = (1..20_000).group_by{|n| n.proper_divisors.size}.max select.each do |n|
puts "#{n} has #{size} divisors"
end</lang>
- Output:
1: [] 2: [1] 3: [1] 4: [1, 2] 5: [1] 6: [1, 2, 3] 7: [1] 8: [1, 2, 4] 9: [1, 3] 10: [1, 2, 5] 15120 has 79 divisors 18480 has 79 divisors
An Alternative Approach
<lang ruby>#Determine the integer within a range of integers that has the most proper divisors
- Nigel Galloway: December 23rd., 2014
require "prime" n, g = 0 (1..20000).each{|i| e = i.prime_division.inject(1){|n,g| n * (g[1]+1)}
n, g = e, i if e > n}
puts "#{g} has #{n-1} proper divisors"</lang>
- Output:
In the range 1..200000
15120 has 79 proper divisors
and in the ranges 1..2000000 & 1..20000000
166320 has 159 proper divisors 1441440 has 287 proper divisors
Scala
Simple proper divisors
<lang Scala>def properDivisors(n: Int) = (1 to n/2).filter(i => n % i == 0) def format(i: Int, divisors: Seq[Int]) = f"$i%5d ${divisors.length}%2d ${divisors mkString " "}"
println(f" n cnt PROPER DIVISORS") val (count, list) = (1 to 20000).foldLeft( (0, List[Int]()) ) { (max, i) =>
val divisors = properDivisors(i) if (i <= 10 || i == 100) println( format(i, divisors) ) if (max._1 < divisors.length) (divisors.length, List(i)) else if (max._1 == divisors.length) (divisors.length, max._2 ::: List(i)) else max
}
list.foreach( number => println(f"$number%5d ${properDivisors(number).length}") )</lang>
- Output:
n cnt PROPER DIVISORS 1 0 2 1 1 3 1 1 4 2 1 2 5 1 1 6 3 1 2 3 7 1 1 8 3 1 2 4 9 2 1 3 10 3 1 2 5 100 8 1 2 4 5 10 20 25 50 15120 79 18480 79
Proper divisors for big (long) numbers
<lang Scala>import annotation.tailrec import collection.parallel.mutable.ParSeq
def factorize(n: Long): List[Long] = {
@tailrec def factors(tuple: (Long, Long, List[Long], Int)): List[Long] = { tuple match { case (1, _, acc, _) => acc case (n, k, acc, _) if (n % k == 0) => factors((n / k, k, acc ++ ParSeq(k), Math.sqrt(n / k).toInt)) case (n, k, acc, sqr) if (k < sqr) => factors(n, k + 1, acc, sqr) case (n, k, acc, sqr) if (k >= sqr) => factors((1, k, acc ++ ParSeq(n), 0)) } } factors((n, 2, List[Long](), Math.sqrt(n).toInt))
} def properDivisors(n: Long) = {
val factors = factorize(n) val products = (1 until factors.length).map(i => factors.combinations(i).map(_.product).toList).flatten (1L +: products).filter(_ < n)
}</lang>
Swift
Simple function: <lang Swift>func properDivs1(n: Int) -> [Int] {
return filter (1 ..< n) { n % $0 == 0 }
}</lang> More efficient function: <lang Swift>import func Darwin.sqrt
func sqrt(x:Int) -> Int { return Int(sqrt(Double(x))) }
func properDivs(n: Int) -> [Int] {
if n == 1 { return [] } var result = [Int]() for div in filter (1 ... sqrt(n), { n % $0 == 0 }) { result.append(div)
if n/div != div && n/div != n { result.append(n/div) } } return sorted(result)
}</lang> Rest of the task: <lang Swift>for i in 1...10 {
println("\(i): \(properDivs(i))")
}
var (num, max) = (0,0)
for i in 1...20_000 {
let count = properDivs(i).count if (count > max) { (num, max) = (i, count) }
}
println("\(num): \(max)")</lang>
- Output:
1: [] 2: [1] 3: [1] 4: [1, 2] 5: [1] 6: [1, 2, 3] 7: [1] 8: [1, 2, 4] 9: [1, 3] 10: [1, 2, 5] 15120: 79
Tcl
Note that if a number, , greater than 1 divides exactly, both and are proper divisors. (The raw answers are not sorted; the pretty-printer code sorts.) <lang tcl>proc properDivisors {n} {
if {$n == 1} return set divs 1 for {set i 2} {$i*$i <= $n} {incr i} {
if {!($n % $i)} { lappend divs $i if {$i*$i < $n} { lappend divs [expr {$n / $i}] } }
} return $divs
}
for {set i 1} {$i <= 10} {incr i} {
puts "$i => {[join [lsort -int [properDivisors $i]] ,]}"
} set maxI [set maxC 0] for {set i 1} {$i <= 20000} {incr i} {
set c [llength [properDivisors $i]] if {$c > $maxC} {
set maxI $i set maxC $c
}
} puts "max: $maxI => (...$maxC…)"</lang>
- Output:
1 => {} 2 => {1} 3 => {1} 4 => {1,2} 5 => {1} 6 => {1,2,3} 7 => {1} 8 => {1,2,4} 9 => {1,3} 10 => {1,2,5} max: 15120 => (...79...)
zkl
<lang zkl>fcn properDivs(n){ [1.. (n + 1)/2 + 1].filter('wrap(x){ n%x==0 and n!=x }) } [1..10].apply(properDivs).println(); [1..20_001].apply('wrap(n){ T(properDivs(n).len(),n) })
.reduce(fcn([(a,_)]ab, [(c,_)]cd){ a>c and ab or cd },T(0,0)) .println();</lang>
- Output:
L(L(),L(1),L(1),L(1,2),L(1),L(1,2,3),L(1),L(1,2,4),L(1,3),L(1,2,5)) L(79,18480)