Calmo numbers: Difference between revisions
Add Scala implementation
(→{{header|Quackery}}: replaced isprime not with factors size 2 !=) |
(Add Scala implementation) |
||
| (11 intermediate revisions by 5 users not shown) | |||
Line 73:
print( ( newline ) )
END
</syntaxhighlight>
{{out}}
<pre>
165 273 385 399 561 595 665 715 957
</pre>
=={{header|ALGOL W}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="algolw">
begin % find some "Calmo" numbers: numbers n such that they have 3k divisors %
% (other than 1 and n) for some k > 0 and the sum of their divisors %
% taken three at a time is a prime %
integer MAX_NUMBER, MAX_PRIME;
MAX_NUMBER := 1000; % largest number we will consider %
MAX_PRIME := MAX_NUMBER * 3; % largest prime we need to consider %
% as we are going to sum divisors in groups of three, %
% it should be (more than) large enough %
begin
logical array prime ( 1 :: MAX_PRIME );
integer array dsum, dcount ( 1 :: MAX_NUMBER );
% sieve the primes to MAX_PRIME %
for i := 1 until MAX_PRIME do prime( i ) := true;
prime( 1 ) := false;
for i := 2 until truncate( sqrt( MAX_PRIME ) ) do begin
if prime( i ) then begin
for p := i * i step i until MAX_PRIME do prime( p ) := false
end if_prime_i
end for_i ;
% construct tables of the divisor counts and divisor sums and check %
% for the numbers as we do it %
% as we are ignoring 1 and n, the initial counts and sums will be 0 %
% but we should ignore primes %
for i := 1 until MAX_NUMBER do begin
dsum( i ) := dcount( i ) := if prime( i ) then -1 else 0
end for_i ;
for i := 2 until MAX_NUMBER do begin
for j := i + i step i until MAX_NUMBER do begin
% have another proper divisor %
if dsum( j ) >= 0 then begin
% this number is still a candidate %
dsum( j ) := dsum( j ) + i;
dcount( j ) := dcount( j ) + 1;
if dcount( j ) = 3 then begin
% the divisor count is currently 3 %
% if then divisor sum isn't prime, ignore it in future %
% if the divisor sum is prime, reset the sum and count %
dsum( j ) := dcount( j ) :=
if NOT prime( dsum( j ) ) then - 1 else 0
end if_dcount_j_eq_3
end if_dsum_j_ge_0
end for_j
end for_i ;
% show the numbers %
for i := 2 until MAX_NUMBER do begin
if dcount( i ) = 0 then writeon( i_w := 1, s_w := 0, " ", i )
end for_i ;
end
end.
</syntaxhighlight>
{{out}}
Line 606 ⟶ 666:
957 [3 11 29 33 87 319] [43 439]
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang=Haskell>import Data.List (group, sort)
import Data.List.Split (chunksOf)
import Data.Numbers.Primes (isPrime, primeFactors)
---------------------- CALMO NUMBERS ---------------------
isCalmo :: Int -> Bool
isCalmo n =
let xs = properDivisors n
m = length xs
in m > 3
&& 0 == mod (pred m) 3
&& all (isPrime . sum) (chunksOf 3 $ tail xs)
--------------------------- TEST -------------------------
main :: IO ()
main = print $ takeWhile (< 1000) $ filter isCalmo [1 ..]
------------------------- GENERIC ------------------------
properDivisors :: Int -> [Int]
properDivisors =
init
. sort
. foldr --
(flip ((<*>) . fmap (*)) . scanl (*) 1)
[1]
. group
. primeFactors</syntaxhighlight>
{{Out}}
<pre>[165,273,385,399,561,595,665,715,957]</pre>
=={{header|J}}==
Line 617 ⟶ 713:
(This implementation relies on infinity not being specifically prime nor non-prime, and on treating the error case as "not a Calmo number").
=={{header|JavaScript}}==
{{Trans|ALGOL 68}}
Procedural, uses console.log to show the numbers.
<syntaxhighlight lang="javascript">
{ // find some "Calmo" numbers: numbers n such that they have 3k divisors
// (other than 1 and n) for some k > 0 and the sum of their divisors
// taken three at a time is a prime
'use strict'
const maxNumber = 1000 // largest number we will consider
// construct a sieve of (hopefully) enough primes - as we are going to sum
// the divisors in groups of three, it should be (more than) large enough
let isPrime = []
const maxPrime = maxNumber * 3
for( let sPos = 1; sPos <= maxPrime; sPos ++ ){ isPrime[ sPos ] = sPos % 2 == 1 }
isPrime[ 1 ] = false
isPrime[ 2 ] = true
const rootMaxPrime = Math.floor( Math.sqrt( maxPrime ) )
for( let sPos = 3; sPos <= rootMaxPrime; sPos += 2 ) {
if( isPrime[ sPos ] ){
for( let p = sPos * sPos; p <= maxPrime; p += sPos ){ isPrime[ p ] = false }
}
}
// construct tables of the divisor counts and divisor sums and check for
// the numbers as we do it
// as we are ignoring 1 and n, the initial counts and sums will be 0
// but we should ignore primes
let dsum = [], dcount = []
for( let i = 1; i <= maxNumber; i ++ ){
dsum[ i ] = dcount[ i ] = ( isPrime[ i ] ? -1 : 0 )
}
for( let i = 2; i <= maxNumber; i ++ ){
for( let j = i + i; j <= maxNumber; j += i ){
// have another proper divisor
if( dsum[ j ] >= 0 ){
// this number is still a candidate
dsum[ j ] = dsum[ j ] + i
dcount[ j ] = dcount[ j ] + 1
if( dcount[ j ] == 3 ){
// the divisor count is currently 3
// if the divisor sum isn't prime, ignore it in future
// if the divisor sum is prime, reset the sum and count
dsum[ j ] = dcount[ j ] = ( ! isPrime[ dsum[ j ] ] ? -1 : 0 )
}
}
}
}
// show the numbers, they will have 0 in the divisor count
let calmoNumbers = []
for( let i = 2; i <= maxNumber; i ++ ){
if( dcount[ i ] == 0 ){
calmoNumbers.push( i )
}
}
console.log( calmoNumbers )
}
</syntaxhighlight>
{{out}}
<pre>
[ 165, 273, 385, 399, 561, 595, 665, 715, 957 ]
</pre>
Or, by functional composition, and preferring to return a value directly (avoiding `console.log`, which is not defined in ECMAScript, and is not available to all JS interpreters):
<syntaxhighlight lang="javascript">(() => {
"use strict";
// ------------------ CALMO NUMBERS ------------------
// isCalmo :: Int -> Bool
const isCalmo = n => {
const
ds = properDivisors(n),
nd = ds.length;
return 3 < nd && (
0 === (nd - 1) % 3
) && chunksOf(3)(ds.slice(1)).every(
triple => isPrime(sum(triple))
);
};
// ---------------------- TEST -----------------------
const main = () =>
enumFromTo(1)(1000).filter(
isCalmo
);
// --------------------- GENERIC ---------------------
// chunksOf :: Int -> [a] -> [[a]]
const chunksOf = n => {
// xs split into sublists of length n.
// The last sublist will be short if n
// does not evenly divide the length of xs .
const go = xs => {
const chunk = xs.slice(0, n);
return 0 < chunk.length
? [chunk, ...go(xs.slice(n))]
: [];
};
return go;
};
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = m =>
n => Array.from({
length: 1 + n - m
}, (_, i) => m + i);
// enumFromThenTo :: Int -> Int -> Int -> [Int]
const enumFromThenTo = m =>
// Integer values enumerated from m to n
// with a step defined by (nxt - m).
nxt => n => {
const d = nxt - m;
return Array.from({
length: (Math.floor(n - nxt) / d) + 2
}, (_, i) => m + (d * i));
};
// isPrime :: Int -> Bool
const isPrime = n => {
// True if n is prime.
if (n === 2 || n === 3) {
return true;
}
if (2 > n || 0 === (n % 2)) {
return false;
}
if (9 > n) {
return true;
}
if (0 === (n % 3)) {
return false;
}
const p = x =>
0 === n % x || 0 === (n % (2 + x));
return !enumFromThenTo(5)(11)(1 + Math.sqrt(n))
.some(p);
};
// properDivisors :: Int -> [Int]
const properDivisors = n => {
const
rRoot = Math.sqrt(n),
intRoot = Math.floor(rRoot),
lows = enumFromTo(1)(intRoot)
.filter(x => 0 === (n % x));
return lows.concat(
lows.map(x => n / x)
.reverse()
.slice(
rRoot === intRoot
? 1
: 0,
-1
)
);
};
// sum :: [Num] -> Num
const sum = xs =>
// The numeric sum of all values in xs.
xs.reduce((a, x) => a + x, 0);
// MAIN ---
return JSON.stringify(main());
})();</syntaxhighlight>
{{Out}}
<pre>[165,273,385,399,561,595,665,715,957]</pre>
=={{header|Julia}}==
Line 633 ⟶ 916:
println(filter(isCalmo, 1:1000))
</syntaxhighlight>
=={{header|Lua}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="lua">
do --[[ find some "Calmo" numbers: numbers n such that they have 3k divisors
(other than 1 and n) for some k > 0 and the sum of their divisors
taken three at a time is a prime
--]]
local maxNumber = 1000 -- largest number we will consider
-- construct a sieve of (hopefully) enough primes - as we are going to sum
-- the divisors in groups of three, it should be (more than) large enough
local isPrime, maxPrime = {}, maxNumber * 2
for sPos = 1, maxPrime do isPrime[ sPos ] = sPos % 2 == 1 end
isPrime[ 1 ] = false
isPrime[ 2 ] = true
for sPos = 3, math.sqrt( maxPrime ), 2 do
if isPrime[ sPos ] then
for p = sPos * sPos, maxPrime, sPos do isPrime[ p ] = false end
end
end
-- construct tables of the divisor counts and divisor sums and check for
-- the numbers as we do it
-- as we are ignoring 1 and n, the initial counts and sums will be 0
-- but we should ignore primes
local dsum, dcount = {}, {}
for i = 1, maxNumber do
dcount[ i ] = ( isPrime[ i ] and -1 or 0 )
dsum[ i ] = dcount[ i ]
end
for i = 2, maxNumber do
for j = i + i, maxNumber, i do
-- have another proper divisor
if dsum[ j ] >= 0 then
-- this number is still a candidate
dsum[ j ] = dsum[ j ] + i
dcount[ j ] = dcount[ j ] + 1
if dcount[ j ] == 3 then
-- the divisor count is currently 3
-- if the divisor sum isn't prime, ignore it in future
-- if the divisor sum is prime, reset the sum and count
dcount[ j ] = ( not isPrime[ dsum[ j ] ] and -1 or 0 )
dsum[ j ] = dcount[ j ]
end
end
end
end
-- show the numbers, they will have 0 in the divisor count
for i = 2, maxNumber do
if dcount[ i ] == 0 then
io.write( " ", i )
end
end
io.write( "\n" )
end
</syntaxhighlight>
{{out}}
<pre>
165 273 385 399 561 595 665 715 957
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="Mathematica">
(*Function to get the divisors of a number excluding 1 and the number itself*)
EligibleDivisors[n_Integer] :=
Select[Divisors[n], # != 1 && # != n &]
(*Function to check if the sum of every three consecutive eligible divisors is prime*)
IsCalmoNumber[n_Integer] :=
Module[{divisors, sums, divisorsLength},
divisors = EligibleDivisors[n];
divisorsLength = Length[divisors];
If[Mod[divisorsLength, 3] != 0 || divisorsLength <= 0,
Return[False]];
sums = Total /@ Partition[divisors, 3];
AllTrue[sums, PrimeQ]
]
(*Find all Calmo numbers under 1000*)
calmoNumbers = Select[Range[2, 999], IsCalmoNumber]
(*Output the Calmo numbers*)
calmoNumbers // Print
</syntaxhighlight>
{{out}}
<pre>
{165, 273, 385, 399, 561, 595, 665, 715, 957}
</pre>
=={{header|MiniScript}}==
<syntaxhighlight lang="miniscript">
isPrime = function(n)
if n < 2 then return false
if n < 4 then return true
for i in range(2,floor(n ^ 0.5))
if n % i == 0 then return false
end for
return true
end function
getFactors = function(n)
factors = {}
for i in range(1, floor(n ^ 0.5))
if n % i == 0 then
factors[i] = 1
factors[n /i ] = 1
end if
end for
return factors.indexes.sort
end function
isCalmo = function(n)
factors = getFactors(n)
if not(factors.len >= 5 and (factors.len - 2) % 3 == 0) then return false
for i in range(1, factors.len - 4, 3)
if not isPrime(factors[i] + factors[i+1] + factors[i+2]) then return false
end for
return true
end function
for i in range(1, 1000)
if isCalmo(i) then print i
end for
</syntaxhighlight>
{{out}}
<pre>165
273
385
399
561
595
665
715
957
</pre>
=={{header|Nim}}==
Line 671 ⟶ 1,091:
<pre> 165 273 385 399 561 595 665 715 957
</pre>
=={{header|PARI/GP}}==
<syntaxhighlight lang="PARI/GP">
\\ Function to get the divisors of a number excluding 1 and the number itself
eligibleDivisors(n) = {
my(divs = divisors(n)); \\ Compute all divisors of n
if (#divs <= 2, return([])); \\ If there are no divisors other than 1 and n, return an empty list
vecextract(divs, "2..-2"); \\ Extract divisors without the first and last elements (1 and n)
};
\\ Function to check if the sum of every three consecutive eligible divisors is prime
isCalmoNumber(n) = {
my(divisors, sums, i, k);
divisors = eligibleDivisors(n); \\ Get eligible divisors
if ((#divisors % 3 != 0) || (#divisors == 0), return(0)); \\ If not divisible by 3 or no divisors, return false
sums = vector(#divisors \ 3, i, sum(k = 1, 3, divisors[3*i + k - 3])); \\ Compute sums of every three divisors
for (i = 1, #sums,
if (!isprime(sums[i]), return(0)); \\ If any sum is not prime, return false
);
return(1); \\ If all sums are prime, return true
};
{
\\ Find all Calmo numbers under 1000
calmoNumbers = [];
for (n = 1, 1000,
if (isCalmoNumber(n), calmoNumbers = concat(calmoNumbers, n)); \\ Check if n is a Calmo number and add to the list
);
print(calmoNumbers); \\ Print all Calmo numbers found under 1000
}
</syntaxhighlight>
{{out}}
<pre>
[165, 273, 385, 399, 561, 595, 665, 715, 957]
</pre>
=={{header|Perl}}==
Line 959 ⟶ 1,420:
</pre>
Runs in 2 minutes 54 seconds on a HP-50g.
=={{header|Scala}}==
{{trans|Python}}
<syntaxhighlight lang="Scala">
object Main extends App {
def isPrime(n: Int): Boolean = {
for (i <- 2 to math.sqrt(n).toInt) {
if (n % i == 0) {
return false
}
}
true
}
def isCalmo(n: Int): Boolean = {
val limite = math.sqrt(n)
var cont = 0
var sumD = 0
var sumQ = 0
var k = 0
var q = 0
var d = 2
while (d < limite) {
q = n / d
if (n % d == 0) {
cont += 1
sumD += d
sumQ += q
if (cont == 3) {
k += 3
if (!isPrime(sumD)) {
return false
}
if (!isPrime(sumQ)) {
return false
}
cont = 0
sumD = 0
sumQ = 0
}
}
d += 1
}
if (cont != 0 || k == 0) {
return false
}
true
}
for (n <- 1 until 1000) {
if (isCalmo(n)) {
print(n + " ")
}
}
}
</syntaxhighlight>
{{out}}
<pre>
165 273 385 399 561 595 665 715 957
</pre>
=={{header|Wren}}==
Line 964 ⟶ 1,488:
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./seq" for Lst
import "./fmt" for Fmt
| |||