Proper divisors: Difference between revisions

{{trans|Python}}

R Array(Set((1 .. (n + 1) I/ 2).filter(x -> @n % x == 0 & @n != x)))

V (n, leng) = max(((1..20000).map(n -> (n, proper_divs(n).len))), key' pd -> pd[1])

{{out}}

{{trans|Rexx}}

This program uses two ASSIST macros (XDECO, XPRNT) to keep the code as short as possible.

PROPDIV CSECT

USING PROPDIV,R13 base register

XDEC DS CL12

YREGS

{{out}}

<pre>

=={{header|Action!}}==

Calculations on a real Atari 8-bit computer take quite long time. It is recommended to use an emulator capable with increasing speed of Atari CPU.

INT i,max

BYTE count

OD

PrintF("%I has %I proper divisors%E",ind,max)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Proper_divisors.png Screenshot from Atari 8-bit computer]

[[http://rosettacode.org/wiki/Amicable_pairs#Ada]], we define this routine as a function of a generic package:

type Result_Type (<>) is limited private;

None: Result_Type;

else Process(N, First+1));

Now we instantiate the ''generic package'' to solve the other two parts of the task. Observe that there are two different instantiations of the package: one to generate a list of proper divisors, another one to count the number of proper divisors without actually generating such a list:

procedure Proper_Divisors is

Natural'Image(Number_Count) & " proper divisors.");

end;

{{out}}

===As required by the Task===

{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}

MODE DIVISORLIST = STRUCT( INT divisor, REF DIVISORLIST next );

, " divisors"

, newline

{{out}}

<pre>

Alternative version that uses a sieve-like approach for faster proper divisor counting.

<br><br>Note, in order to run this with Algol 68G under Windows (and possibly Linux) the heap size must be increased, see [[ALGOL_68_Genie#Using_a_Large_Heap]].

# find the first/only number in 1 : 20 000 and 1 : 64 000 000 with #

# the most divisors #

max number := 64 000 000

OD

{{out}}

=={{header|ALGOL-M}}==

Algol-M's maximum allowed integer value of 16,383 prevented searching up to 20,000 for the number with the most divisors, so the code here searches only up to 10,000.

BEGIN

END

{{out}}

<pre>

===Functional===

{{Trans|JavaScript}}

-- properDivisors :: Int -> [Int]

end script

end if

{{Out}}

{num:4, divisors:{1, 2}}, {num:5, divisors:{1}}, {num:6, divisors:{1, 2, 3}},

{num:7, divisors:{1}}, {num:8, divisors:{1, 2, 4}}, {num:9, divisors:{1, 3}},

{num:10, divisors:{1, 2, 5}}},

----

===Idiomatic===

set output to {}

set output to output as text

set AppleScript's text item delimiters to astid

{{output}}

2's proper divisors: {1}

3's proper divisors: {1}

Largest number of proper divisors for any number from 1 to 20,000: 79

=={{header|Arc}}==

;; Given num, return num and the list of its divisors

(div-lists 20000)

;; This took about 10 minutes on my machine.

{{Out}}

(1 0)

(2 1)

It is the number 18480.

There are 2 numbers with this trait, and they are (18480 15120)

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program proFactor.s */

/***************************************************/

.include "../affichage.inc"

{{Output}}

<pre>

=={{header|Arturo}}==

(factors x) -- x

]

{{out}}

=={{header|AutoHotkey}}==

Array := []

if n = 1

Array[i] := true

return Array

loop, 10

{

output .= "`nNumber(s) in the range 1 to 20,000 with the most proper divisors:`n" numDiv.Pop() " with " maxDiv " divisors"

MsgBox % output

{{out}}

<pre>Number Divisors Count

=={{header|AWK}}==

# syntax: GAWK -f PROPER_DIVISORS.AWK

BEGIN {

return

}

<p>output:</p>

<pre>

{{works with|QBasic|1.1}}

{{works with|QuickBasic|4.5}}

IF number < 2 THEN CountProperDivisors = 0

count = 0

PRINT

PRINT most; " has the most proper divisors, namely "; maxCount

{{out}}

<pre>

==={{header|BASIC256}}===

if limit < 1 then return

for i = 1 to limit

print

print most; " has the most proper divisors, namely "; maxCount

{{out}}

<pre>

==={{header|True BASIC}}===

IF number < 2 THEN LET CountProperDivisors = 0

LET count = 0

PRINT

PRINT most; "has the most proper divisors, namely"; maxCount

{{out}}

<pre>

==={{header|Yabasic}}===

if limit < 1 then return : fi

for i = 1 to limit

print

print most, " has the most proper divisors, namely ", maxCount

{{out}}

<pre>

=={{header|BaCon}}==

FUNCTION ProperDivisor(nr, show)

PRINT "Most proper divisors for number in the range 1-20000: ", MagicNumber, " with ", MaxDivisors, " divisors."

{{out}}

<pre>

===Brute Force===

C has tedious boilerplate related to allocating memory for dynamic arrays, so we just skip the problem of storing values altogether.

#include <stdio.h>

#include <stdbool.h>

return 0;

}

{{out}}

<pre>

===Number Theoretic===

There is no need to go through all the divisors if only the count is needed, this implementation refines the brute force approach by solving the second part of the task via a Number Theory formula. The running time is noticeably faster than the brute force method above. Output is same as the above.

#include <stdio.h>

#include <stdbool.h>

return 0;

}

=={{header|C sharp}}==

{

using System;

}

}

{{out}}

<pre>1: {}

=={{header|C++}}==

#include <iostream>

#include <algorithm>

return 0 ;

}

{{out}}

<pre>

=={{header|Ceylon}}==

function divisors(Integer int) =>

print("the number(s) with the most divisors between ``start`` and ``end`` is/are:

``mostDivisors?.item else "nothing"`` with ``mostDivisors?.key else "no"`` divisors");

{{out}}

<pre>1 => []

=={{header|Clojure}}==

(:gen-class))

(println n " has " (count factors) " divisors"))

{{Output}}

<pre>

=={{header|Common Lisp}}==

Ideally, the smallest-divisor function would only try prime numbers instead of odd numbers.

"(int,list)->list::Function to find all proper divisors of a +ve integer."

(dotimes (i 10) (format t "~A:~A~%" (1+ i) (proper-divisors-recursive (1+ i))))

(format t "Task 2:Count & list of numbers <=20,000 with the most Proper Divisors:~%~A~%"

{{out}}

<pre>CL-USER(10): (main)

=={{header|Component Pascal}}==

{{Works with|Black Box Component Builder}}

MODULE RosettaProperDivisor;

IMPORT StdLog;

^Q RosettaProperDivisor.Do~

{{out}}

<pre>

{{trans|Python}}

Currently the lambda of the filter allocates a closure on the GC-managed heap.

import std.stdio, std.algorithm, std.range, std.typecons;

iota(1, 11).map!properDivs.writeln;

iota(1, 20_001).map!(n => tuple(properDivs(n).count, n)).reduce!max.writeln;

{{out}}

<pre>[[], [1], [1], [1, 2], [1], [1, 2, 3], [1], [1, 2, 4], [1, 3], [1, 2, 5]]

=={{header|Delphi}}==

{{trans|C#}}

program ProperDivisors;

readln;

end.

{{out}}

<pre>

Version with TParallel.For

program ProperDivisors;

readln;

end.

=={{header|Dyalect}}==

{{trans|Swift}}

if n == 1 {

yield break

}

{{out}}

=={{header|EchoLisp}}==

(lib 'list) ;; list-delete

{{out}}

(for ((i (in-range 1 11))) (writeln i (divs i)))

1 null

(lib 'bigint)

(numdivs 95952222101012742144) → 666 ;; 🎩

=={{header|Eiffel}}==

class

APPLICATION

end

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Erlang}}

def divisors(1), do: []

def divisors(n), do: [1 | divisors(2,n,:math.sqrt(n))] |> Enum.sort

IO.puts "#{n}: #{inspect Proper.divisors(n)}"

end)

{{out}}

=={{header|Erlang}}==

-export([divs/1,sumdivs/1,longest/1]).

longest(L,Acc,A,Acc+1);

true -> longest(L,Current,CurLeng,Acc+1)

{{out}}

<pre>

=={{header|F_Sharp|F#}}==

// the simple function with the answer

let propDivs n = [1..n/2] |> List.filter (fun x->n % x = 0)

|> Seq.fold (fun a b ->match a,b with | (_,c1,_),(_,c2,_) when c2 > c1 -> b | _-> a) (0,0,[])

|> fun (n,count,_) -> (n,count,[]) |> show

{{out}}

=={{header|Factor}}==

math.primes.factors math.ranges prettyprint sequences ;

10 [1,b] [ dup pprint bl divisors but-last . ] each

20000 [1,b] [ #divisors ] supremum-by dup #divisors

{{out}}

=={{header|Fermat}}==

[d]:=[(1)]; {start divisor list with just 1, which is a divisor of everything}

for i = 2 to n\2 do {loop through possible divisors of n}

od;

{{out}}<pre>

{{works with|gforth|0.7.3}}

dup 1 ?do

dup i mod 0= if i . then

;

{{out}}

=={{header|Fortran}}==

Compiled using G95 compiler, run on x86 system under Puppy Linux

function icntprop(num )

print *,maxj,' has max proper divisors: ',maxcnt

end

{{out}}

<pre>

=={{header|FreeBASIC}}==

' FreeBASIC v1.05.0 win64

Sleep

End

{{out}}

=={{header|Free Pascal}}==

Program ProperDivisors;

list.free;

End.

{{out}}

<pre>

Frink's built-in factorization routines efficiently find factors of arbitrary-sized integers.

for n = 1 to 10

println["$n\t" + join[" ", properDivisors[n]]]

properDivisors[n] := allFactors[n, true, false, true]

{{out}}

<pre>

=={{header|GFA Basic}}==

OPENW 1

CLEARW 1

RETURN count%-1

ENDFUNC

Output is:

=={{header|Go}}==

{{trans|Kotlin}}

import (

fmt.Println(n)

}

{{out}}

=={{header|Haskell}}==

import Data.List

putStrLn "a number with the most divisors within 1 to 20000 (number, count):"

print $ maximumBy (comparing snd)

{{out}}

<pre>divisors of 1 to 10:

For a little more efficiency, we can filter only up to the root – deriving the higher proper divisors from the lower ones, as quotients:

import Data.Ord (comparing)

import Data.Bool (bool)

print $

maximumBy (comparing snd) $

{{Out}}

<pre>Proper divisors of 1 to 10:

and we can also define properDivisors in terms of primeFactors:

import Data.List (group, maximumBy, sort)

import Data.Ord (comparing)

w = maximum (length . xShow <$> xs)

in unlines $

{{Out}}

<pre>Proper divisors of [1..10]:

So, borrowing from [[Factors of an integer#J|the J implementation]] of that related task:

Proper divisors of numbers 1 through 10:

1 --

2 -- 1

8 -- 1 2 4

9 -- 1 3

Number(s) not exceeding 20000 with largest number of proper divisors (and the count of those divisors):

15120 79

Note that it's a bit more efficient to simply count factors here, when selecting the candidate numbers.

15120 79

We could also arbitrarily toss either 15120 or 18480 (keeping the other number), if it were important that we produce only one result.

=={{header|Java}}==

{{works with|Java|1.5+}}

import java.util.LinkedList;

import java.util.List;

System.out.println(x + ": " + count);

}

{{out}}

<pre>1: []

===ES5===

// Proper divisors

);

{{out}}

===ES6===

'use strict';

// MAIN ---

return main();

{{Out}}

<pre>Proper divisors of [1..10]:

{{works with|jq|1.4}}

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)":

# unordered

( [null, 0];

count( $i | proper_divisors ) as $count

'''The tasks:'''

(range(1;11) as $i | "\($i): \( [ $i | proper_divisors] )"),

"",

"the maximal number proper divisors together with the corresponding",

"count of proper divisors is:",

{{out}}

The proper divisors of the numbers 1 to 10 inclusive are:

1: []

the maximal number proper divisors together with the corresponding

count of proper divisors is:

=={{header|Julia}}==

Use <code>factor</code> to obtain the prime factorization of the target number. I adopted the argument handling style of <code>factor</code> in my <code>properdivisors</code> function.

function properdivisors{T<:Integer}(n::T)

0 < n || throw(ArgumentError("number to be factored must be ≥ 0, got $n"))

println(nlst, " have the maximum proper divisor count of ", maxdiv, ".")

{{out}}

=={{header|Kotlin}}==

fun listProperDivisors(limit: Int) {

println("The following number(s) have the most proper divisors, namely " + maxCount + "\n")

for (n in most) println(n)

{{out}}

{{trans|Go}}

{{works with|langur|0.10}}

val .cntproper = f(.x) for[=0] .i of .x \ 2 { if .x div .i: _for += 1 }

writeln $"The following number(s) <= 20000 have the most proper divisors (\.max;)"

{{out}}

=={{header|Lua}}==

function propDivs (n)

if n < 2 then return {} end

end

end

{{out}}

<pre>1:

A Function that yields the proper divisors of an integer n:

Proper divisors of n from 1 to 10:

{{out}}

<pre>1 {}

The number with the most divisors between 1 and 20,000:

Last[SortBy[{#1, {#2, Length@ProperDivisors[#2]}}, Last]] &,

{0, 0},

{{out}}

<pre>{18480, 79}</pre>

An alternate way to find the number with the most divisors between 1 and 20,000:

Table[

{n, Length@ProperDivisors[n]},

{n, 1, 20000}],

{{out}}

<pre>{15120, 79}</pre>

=={{header|MATLAB}}==

K=1:ceil(N/2);

{{out}}

=={{header|Modula-2}}==

FROM FormatString IMPORT FormatString;

FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

ReadChar

=={{header|Nim}}==

{{trans|C}}

proc properDivisors(n: int) =

maxI = i

{{out}}

<pre>

=={{header|Oberon-2}}==

MODULE ProperDivisors;

IMPORT

END

END ProperDivisors.

{{out}}

<pre>

=={{header|Objeck}}==

class Proper{

}

}

Output:

=={{header|Oforth}}==

10 seq apply(#[ dup print " : " print properDivs println ])

{{out}}

<pre>

=={{header|PARI/GP}}==

apply(proper, [1..10])

{{out}}

<pre>%1 = [[], [2], [3], [2, 4], [5], [2, 3, 6], [7], [2, 4, 8], [3, 9], [2, 5, 10]]

{{works with|Free Pascal}}

Using prime factorisation

uses

sysutils;

j := CntProperDivs(primeDecomp);

PrimeFacOut(primeDecomp);writeln(' ',j:10,' factors'); writeln;

1 :

2 : 1

===Using a module for divisors===

{{libheader|ntheory}}

sub proper_divisors {

my $n = shift;

no warnings 'numeric';

say max(map { scalar(proper_divisors($_)) . " $_" } 1..20000);

{{out}}

<pre>1:

=={{header|Phix}}==

The factors routine is an auto-include. The actual implementation of it, from builtins\pfactors.e is

<span style="color: #008080;">global</span> <span style="color: #008080;">function</span> <span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">include1</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>

<span style="color: #000080;font-style:italic;">--

<span style="color: #008080;">return</span> <span style="color: #000000;">lfactors</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">hfactors</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>

The compiler knows where to find that, so the main program is just:

<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d: %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)})</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d divisors: %v\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">maxd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">candidates</span><span style="color: #0000FF;">})</span>

{{out}}

<pre>

=={{header|PHP}}==

function ProperDivisors($n) {

yield 1;

echo "They have ", key($divisorsCount), " divisors.\n";

Outputs:

=={{header|Picat}}==

println(11111=proper_divisors(11111)),

nl,

println(maxN=MaxN),

println(maxLen=MaxLen),

{{out}}

===Larger tests===

Some larger tests of most number of divisors:

time(find_most_divisors(100_000)),

nl,

time(find_most_divisors(1_000_000)),

{{out}}

=={{header|PicoLisp}}==

(de propdiv (N)

(head -1 (filter

(mapcar propdiv (range 1 10))

# Output:

===Brute-force===

(cdr

(rot

(maxi

countdiv

===Factorization===

(if (assoc Key (val Var))

(con @ (inc (cdr @)))

factor

(range 1 20000) )

Output:

<pre>

=={{header|PL/I}}==

(subrg):

cpd: Proc Options(main);

End;

{{out}}

<pre>

=={{header|PowerShell}}==

===version 1===

function proper-divisor ($n) {

if($n -ge 2) {

"$(proper-divisor 496)"

"$(proper-divisor 2048)"

===version 2===

function proper-divisor ($n) {

if($n -ge 2) {

"$(proper-divisor 496)"

"$(proper-divisor 2048)"

===version 3===

function eratosthenes ($n) {

if($n -gt 1){

"$(proper-divisor 496)"

"$(proper-divisor 2048)"

<b>Output:</b>

<pre>

Taking a cue from [http://stackoverflow.com/a/171779 an SO answer]:

UpperBound is round(sqrt(N)),

between(1, UpperBound, D),

proper_divisor_count(N, Count) ),

max(MaxCount, Num) ),

Output:

2:[1]

3:[1]

?- find_most_proper_divisors_in_range(1,20000,Result).

Result = num(15120)-divisor_count(79).

=={{header|PureBasic}}==

EnableExplicit

CloseConsole()

EndIf

{{out}}

===Python: Literal===

A very literal interpretation

... return {x for x in range(1, (n + 1) // 2 + 1) if n % x == 0 and n != x}

...

>>> length

79

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.

from functools import lru_cache, reduce

from collections import Counter

print([proper_divs(n) for n in range(1, 11)])

{{out}}

Defining a list of proper divisors in terms of the prime factorization:

{{Works with|Python|3.7}}

from itertools import accumulate, chain, groupby, product

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>Proper divisors of [1..10]:

=== Python: The Simple Way ===

Not all the code submitters realized that it's a tie for the largest number of factors inside the limit. The task description clearly indicates only one answer is needed. But both numbers are provided for the curious. Also shown is the result for 25000, as there is no tie for that, just to show the program can handle either scenario.

factors = []

for divisor in range(1,1+num//2):

print()

showcount(20000)

{{out}}

<pre style="white-space: pre-wrap;">There are no proper divisors of 1

<code>factors</code> is defined at [[Factors of an integer#Quackery]].

10 times [ i^ 1+ properdivisors echo cr ]

else drop ]

swap echo say " has "

{{out}}

===Package solution===

{{Works with|R|3.3.2 and above}}

require(numbers);

V <- sapply(1:20000, Sigma, k = 0, proper = TRUE); ind <- which(V==max(V));

{{Output}}

===Filter solution===

properDivisors <- function(N) Filter(function(x) N %% x == 0, seq_len(N %/% 2))

" proper divisors.")

}

{{Output}}

=== Short version ===

(require math)

(define (proper-divisors n) (drop-right (divisors n) 1))

(if (< (length (cdr best)) (length divs)) (cons n divs) best)))

(printf "~a has ~a proper divisors\n"

{{out}}

The '''main''' module will only be executed when this file is executed. When used as a library, it will not be used.

(provide fold-divisors ; name as per "Abundant..."

proper-divisors)

#:when [> c C])

(values c i)))

The output is the same as the short version above.

There really isn't any point in using concurrency for a limit of 20_000. The setup and bookkeeping drowns out any benefit. Really doesn't start to pay off until the limit is 50_000 and higher. Try swapping in the commented out race map iterator line below for comparison.