Zumkeller numbers: Difference between revisions
Content added Content deleted
(lang tag update) Tag: Reverted |
Tag: Rollback |
||
Line 37: | Line 37: | ||
{{trans|D}} |
{{trans|D}} |
||
< |
<lang 11l>F getDivisors(n) |
||
V divs = [1, n] |
V divs = [1, n] |
||
V i = 2 |
V i = 2 |
||
Line 145: | Line 145: | ||
=={{header|AArch64 Assembly}}== |
=={{header|AArch64 Assembly}}== |
||
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
||
< |
<lang AArch64 Assembly> |
||
/* ARM assembly AARCH64 Raspberry PI 3B */ |
/* ARM assembly AARCH64 Raspberry PI 3B */ |
||
/* program zumkellex641.s */ |
/* program zumkellex641.s */ |
||
Line 661: | Line 661: | ||
On my machine, this takes about 0.28 seconds to perform the two main searches and a further 107 to do the stretch task. However, the latter time can be dramatically reduced to 1.7 seconds with the cheat of knowing beforehand that the first 200 or so odd Zumkellers not ending with 5 are divisible by 63. The "abundant number" optimisation's now used with odd numbers, but the cheat-free running time was only two to three seconds longer without it. |
On my machine, this takes about 0.28 seconds to perform the two main searches and a further 107 to do the stretch task. However, the latter time can be dramatically reduced to 1.7 seconds with the cheat of knowing beforehand that the first 200 or so odd Zumkellers not ending with 5 are divisible by 63. The "abundant number" optimisation's now used with odd numbers, but the cheat-free running time was only two to three seconds longer without it. |
||
< |
<lang applescript>-- Sum n's proper divisors. |
||
on aliquotSum(n) |
on aliquotSum(n) |
||
if (n < 2) then return 0 |
if (n < 2) then return 0 |
||
Line 822: | Line 822: | ||
{{output}} |
{{output}} |
||
< |
<lang applescript>"1st 220 Zumkeller numbers: |
||
6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 |
6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 |
||
102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 |
102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 |
||
Line 849: | Line 849: | ||
=={{header|ARM Assembly}}== |
=={{header|ARM Assembly}}== |
||
{{works with|as|Raspberry Pi}} |
{{works with|as|Raspberry Pi}} |
||
< |
<lang ARM Assembly> |
||
/* ARM assembly Raspberry PI */ |
/* ARM assembly Raspberry PI */ |
||
/* program zumkeller4.s */ |
/* program zumkeller4.s */ |
||
Line 1,560: | Line 1,560: | ||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<lang csharp>using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using System.Linq; |
using System.Linq; |
||
Line 1,684: | Line 1,684: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<lang cpp>#include <iostream> |
||
#include <cmath> |
#include <cmath> |
||
#include <vector> |
#include <vector> |
||
Line 1,871: | Line 1,871: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<lang d>import std.algorithm; |
||
import std.stdio; |
import std.stdio; |
||
Line 1,991: | Line 1,991: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
This task uses [https://rosettacode.org/wiki/Sum_of_divisors#F.23] |
This task uses [https://rosettacode.org/wiki/Sum_of_divisors#F.23] |
||
< |
<lang fsharp> |
||
// Zumkeller numbers: Nigel Galloway. May 16th., 2021 |
// Zumkeller numbers: Nigel Galloway. May 16th., 2021 |
||
let rec fG n g=match g with h::_ when h>=n->h=n |h::t->fG n t || fG(n-h) t |_->false |
let rec fG n g=match g with h::_ when h>=n->h=n |h::t->fG n t || fG(n-h) t |_->false |
||
Line 2,013: | Line 2,013: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.99 2019-10-06}} |
{{works with|Factor|0.99 2019-10-06}} |
||
< |
<lang factor>USING: combinators grouping io kernel lists lists.lazy math |
||
math.primes.factors memoize prettyprint sequences ; |
math.primes.factors memoize prettyprint sequences ; |
||
Line 2,085: | Line 2,085: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<lang go>package main |
||
import "fmt" |
import "fmt" |
||
Line 2,208: | Line 2,208: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
{{Trans|Python}} |
{{Trans|Python}} |
||
< |
<lang haskell>import Data.List (group, sort) |
||
import Data.List.Split (chunksOf) |
import Data.List.Split (chunksOf) |
||
import Data.Numbers.Primes (primeFactors) |
import Data.Numbers.Primes (primeFactors) |
||
Line 2,313: | Line 2,313: | ||
=={{header|J}}== |
=={{header|J}}== |
||
Implementation:< |
Implementation:<lang J>divisors=: {{ \:~ */@>,{ (^ i.@>:)&.>/ __ q: y }} |
||
zum=: {{ |
zum=: {{ |
||
if. 2|s=. +/divs=. divisors y do. 0 |
if. 2|s=. +/divs=. divisors y do. 0 |
||
Line 2,321: | Line 2,321: | ||
}}@></lang> |
}}@></lang> |
||
Task examples:< |
Task examples:<lang J> 10 22$1+I.zum 1+i.1000 NB. first 220 Zumkeller numbers |
||
6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 |
6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 |
||
108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 |
108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 |
||
Line 2,343: | Line 2,343: | ||
1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377</lang> |
1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377</lang> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<lang java> |
||
import java.util.ArrayList; |
import java.util.ArrayList; |
||
import java.util.Collections; |
import java.util.Collections; |
||
Line 2,497: | Line 2,497: | ||
generates a stream of partitions is easily transformed into a |
generates a stream of partitions is easily transformed into a |
||
specialized function that prunes irrelevant partitions efficiently. |
specialized function that prunes irrelevant partitions efficiently. |
||
< |
<lang jq># The factors, sorted |
||
def factors: |
def factors: |
||
. as $num |
. as $num |
||
Line 2,563: | Line 2,563: | ||
end |
end |
||
| true) |
| true) |
||
// false;</lang>< |
// false;</lang><lang jq>## The tasks: |
||
"First 220:", limit(220; range(2; infinite) | select(is_zumkeller)), |
"First 220:", limit(220; range(2; infinite) | select(is_zumkeller)), |
||
Line 2,589: | Line 2,589: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<lang julia>using Primes |
||
function factorize(n) |
function factorize(n) |
||
Line 2,671: | Line 2,671: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<lang scala>import java.util.ArrayList |
||
import kotlin.math.sqrt |
import kotlin.math.sqrt |
||
Line 2,807: | Line 2,807: | ||
=={{header|Lobster}}== |
=={{header|Lobster}}== |
||
< |
<lang Lobster>import std |
||
// Derived from Julia and Python versions |
// Derived from Julia and Python versions |
||
Line 2,903: | Line 2,903: | ||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
< |
<lang Mathematica>ClearAll[ZumkellerQ] |
||
ZumkellerQ[n_] := Module[{d = Divisors[n], t, ds, x}, |
ZumkellerQ[n_] := Module[{d = Divisors[n], t, ds, x}, |
||
ds = Total[d]; |
ds = Total[d]; |
||
Line 2,936: | Line 2,936: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<lang Nim>import math, strutils |
||
template isEven(n: int): bool = (n and 1) == 0 |
template isEven(n: int): bool = (n and 1) == 0 |
||
Line 3,038: | Line 3,038: | ||
Now using the trick, that one partition sum must include n and improved recursive search.<BR> |
Now using the trick, that one partition sum must include n and improved recursive search.<BR> |
||
Limit is ~1.2e11 |
Limit is ~1.2e11 |
||
< |
<lang pascal>program zumkeller; |
||
//https://oeis.org/A083206/a083206.txt |
//https://oeis.org/A083206/a083206.txt |
||
{$IFDEF FPC} |
{$IFDEF FPC} |
||
Line 3,809: | Line 3,809: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<lang perl>use strict; |
||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 3,883: | Line 3,883: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
<!--< |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">isPartSum</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">isPartSum</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #008080;">if</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
<span style="color: #008080;">if</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
Line 3,964: | Line 3,964: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<lang PicoLisp>(de propdiv (N) |
||
(make |
(make |
||
(for I N |
(for I N |
||
Line 4,046: | Line 4,046: | ||
===Procedural=== |
===Procedural=== |
||
Modified from a footnote at OEIS A083207 (see reference in problem text) by Charles R Greathouse IV. |
Modified from a footnote at OEIS A083207 (see reference in problem text) by Charles R Greathouse IV. |
||
< |
<lang python>from sympy import divisors |
||
from sympy.combinatorics.subsets import Subset |
from sympy.combinatorics.subsets import Subset |
||
Line 4,116: | Line 4,116: | ||
Relying on the standard Python libraries, as an alternative to importing SymPy: |
Relying on the standard Python libraries, as an alternative to importing SymPy: |
||
< |
<lang python>'''Zumkeller numbers''' |
||
from itertools import ( |
from itertools import ( |
||
Line 4,355: | Line 4,355: | ||
{{trans|Zkl}} |
{{trans|Zkl}} |
||
< |
<lang racket>#lang racket |
||
(require math/number-theory) |
(require math/number-theory) |
||
Line 4,419: | Line 4,419: | ||
(formerly Perl 6) |
(formerly Perl 6) |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<lang perl6>use ntheory:from<Perl5> <factor is_prime>; |
||
sub zumkeller ($range) { |
sub zumkeller ($range) { |
||
Line 4,478: | Line 4,478: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
The construction of the partitions were created in the order in which the most likely partitions would match. |
The construction of the partitions were created in the order in which the most likely partitions would match. |
||
< |
<lang rexx>/*REXX pgm finds & shows Zumkeller numbers: 1st N; 1st odd M; 1st odd V not ending in 5.*/ |
||
parse arg n m v . /*obtain optional arguments from the CL*/ |
parse arg n m v . /*obtain optional arguments from the CL*/ |
||
if n=='' | n=="," then n= 220 /*Not specified? Then use the default.*/ |
if n=='' | n=="," then n= 220 /*Not specified? Then use the default.*/ |
||
Line 4,591: | Line 4,591: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<lang ring> |
||
load "stdlib.ring" |
load "stdlib.ring" |
||
Line 4,782: | Line 4,782: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<lang ruby>class Integer |
||
def divisors |
def divisors |
||
Line 4,852: | Line 4,852: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<lang rust> |
||
use std::convert::TryInto; |
use std::convert::TryInto; |
||
Line 4,955: | Line 4,955: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<lang ruby>func is_Zumkeller(n) { |
||
return false if n.is_prime |
return false if n.is_prime |
||
Line 5,002: | Line 5,002: | ||
=={{header|Standard ML}}== |
=={{header|Standard ML}}== |
||
< |
<lang Standard ML> |
||
exception Found of string ; |
exception Found of string ; |
||
Line 5,057: | Line 5,057: | ||
</lang> |
</lang> |
||
call loop and output - interpreter |
call loop and output - interpreter |
||
< |
<lang Standard ML> |
||
- val Zumkellerlist = fn step => fn no5 => |
- val Zumkellerlist = fn step => fn no5 => |
||
let |
let |
||
Line 5,096: | Line 5,096: | ||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<lang swift>import Foundation |
||
extension BinaryInteger { |
extension BinaryInteger { |
||
Line 5,166: | Line 5,166: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<lang vbnet>Module Module1 |
||
Function GetDivisors(n As Integer) As List(Of Integer) |
Function GetDivisors(n As Integer) As List(Of Integer) |
||
Dim divs As New List(Of Integer) From { |
Dim divs As New List(Of Integer) From { |
||
Line 5,295: | Line 5,295: | ||
=={{header|Vlang}}== |
=={{header|Vlang}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<lang vlang>fn get_divisors(n int) []int { |
||
mut divs := [1, n] |
mut divs := [1, n] |
||
for i := 2; i*i <= n; i++ { |
for i := 2; i*i <= n; i++ { |
||
Line 5,418: | Line 5,418: | ||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
I've reversed the order of the recursive calls in the last line of the ''isPartSum'' function which, as noted in the Phix entry, seems to make little difference to Go but (as one might have expected) speeds up this Wren script enormously. The first part is now near instant but was taking several minutes previously. Overall it's now only about 5.5 times slower than Go itself which is a good result for the Wren interpreter. |
I've reversed the order of the recursive calls in the last line of the ''isPartSum'' function which, as noted in the Phix entry, seems to make little difference to Go but (as one might have expected) speeds up this Wren script enormously. The first part is now near instant but was taking several minutes previously. Overall it's now only about 5.5 times slower than Go itself which is a good result for the Wren interpreter. |
||
< |
<lang ecmascript>import "/math" for Int, Nums |
||
import "/fmt" for Fmt |
import "/fmt" for Fmt |
||
import "io" for Stdout |
import "io" for Stdout |
||
Line 5,517: | Line 5,517: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|Julia}} {{trans|Go}} |
{{trans|Julia}} {{trans|Go}} |
||
< |
<lang zkl>fcn properDivs(n){ // does not include n |
||
// if(n==1) return(T); // we con't care about this case |
// if(n==1) return(T); // we con't care about this case |
||
( pd:=[1..(n).toFloat().sqrt()].filter('wrap(x){ n%x==0 }) ) |
( pd:=[1..(n).toFloat().sqrt()].filter('wrap(x){ n%x==0 }) ) |
||
Line 5,541: | Line 5,541: | ||
canSum(sum/2,ds) and n or Void.Skip // sum is even |
canSum(sum/2,ds) and n or Void.Skip // sum is even |
||
}</lang> |
}</lang> |
||
< |
<lang zkl>println("First 220 Zumkeller numbers:"); |
||
zw:=[2..].tweak(isZumkellerW); |
zw:=[2..].tweak(isZumkellerW); |
||
do(11){ zw.walk(20).pump(String,"%4d ".fmt).println() } |
do(11){ zw.walk(20).pump(String,"%4d ".fmt).println() } |