Calmo numbers: Difference between revisions
Content deleted Content added
Added C |
Add Scala implementation |
||
(20 intermediate revisions by 12 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 391 ⟶ 451:
715 [5, 11, 13, 55, 65, 143] [29, 263]
957 [3, 11, 29, 33, 87, 319] [43, 439]
</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
function GetAllProperDivisors(N: Integer;var IA: TIntegerDynArray): integer;
{Make a list of all the "proper dividers" for N}
{Proper dividers are the of numbers the divide evenly into N}
var I: integer;
begin
SetLength(IA,0);
for I:=1 to N-1 do
if (N mod I)=0 then
begin
SetLength(IA,Length(IA)+1);
IA[High(IA)]:=I;
end;
Result:=Length(IA);
end;
var Facts: TIntegerDynArray;
function IsCalmoNumber(N: integer): boolean;
{Test number to see if it a Calmo number}
var Inx,Sum: integer;
begin
Result:=False;
{Get all divisors}
GetAllProperDivisors(N,Facts);
{strip off 1 }
Facts:=Copy(Facts,1,High(Facts));
if Length(Facts)<3 then exit;
{Must be at least three}
if (Length(Facts) mod 3)<>0 then exit;
Inx:=0;
repeat
begin
{Sum three factors}
Sum:=Facts[Inx]+Facts[Inx+1]+Facts[Inx+2];
{Exit if not primve}
if not IsPrime(Sum) then exit;
{Index to next three}
Inc(Inx,3);
end
until Inx>High(Facts)-1;
Result:=True;
end;
procedure ShowCalmoNumbers(Memo: TMemo);
{Show all Calmo numbers less than 1,000}
var I,J: integer;
var S: string;
begin
for I:=1 to 1000 do
if IsCalmoNumber(I) then
begin
S:='';
for J:=0 to High(Facts) do
S:=S+Format('%4d',[Facts[J]]);
S:=Trim(S);
Memo.Lines.Add(IntToStr(I)+' ['+S+']');
end;
end;
</syntaxhighlight>
{{out}}
<pre>
165 [3 5 11 15 33 55]
273 [3 7 13 21 39 91]
385 [5 7 11 35 55 77]
399 [3 7 19 21 57 133]
561 [3 11 17 33 51 187]
595 [5 7 17 35 85 119]
665 [5 7 19 35 95 133]
715 [5 11 13 55 65 143]
957 [3 11 29 33 87 319]
Elapsed Time: 11.747 ms.
</pre>
=={{header|Factor}}==
<syntaxhighlight lang="factor">USING: combinators.short-circuit grouping.extras kernel math
math.functions math.primes math.primes.factors math.vectors
prettyprint ranges sequences sequences.extras ;
IN: calmo
: calmo? ( n -- ? )
divisors 1 -1 rot subseq* {
[ empty? not ]
[ length 3 divisor? ]
[ [ + + prime? ] 3 group-map vall? ]
} 1&& ;
MAIN: [ 2 1000 [a..b) [ calmo? ] filter . ]</syntaxhighlight>
{{out}}
<pre>
V{ 165 273 385 399 561 595 665 715 957 }
</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
local fn IsPrime( n as NSUInteger ) as BOOL
BOOL isPrime = YES
NSUInteger i
if n < 2 then exit fn = NO
if n = 2 then exit fn = YES
if n mod 2 == 0 then exit fn = NO
for i = 3 to int(n^.5) step 2
if n mod i == 0 then exit fn = NO
next
end fn = isPrime
local fn IsCalmo( n as NSUInteger ) as BOOL
BOOL isCalmo = YES
double limit = sqr(n)
NSUInteger count = 0, sumd = 0, sumq = 0, k = 0, q = 0, d = 2
while ( d < limit )
q = n/d
if ( n mod d == 0 )
count++ : sumd += d : sumq += q
if ( count == 3 )
k += 3
if fn IsPrime( sumd ) == NO then exit fn = NO
if fn IsPrime( sumq ) == NO then exit fn = NO
count = 0 : sumd = 0 : sumq = 0
end if
end if
d++
wend
if count != 0 or k == 0 then exit fn = NO
end fn = isCalmo
NSUInteger n
for n = 1 to 1000 -1
if fn IsCalmo( n ) then print n; " ";
next
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
165 273 385 399 561 595 665 715 957
</pre>
Line 452 ⟶ 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 463 ⟶ 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 479 ⟶ 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}}==
<syntaxhighlight lang="Nim">func isPrime(n: Natural): bool =
if n < 2: return false
if (n and 1) == 0: return n == 2
if n mod 3 == 0: return n == 3
var d = 5
var step = 2
while d * d <= n:
if n mod d == 0:
return false
inc d, step
step = 6 - step
return true
func divisors(n: Positive): seq[int] =
for d in 2..<n:
if n mod d == 0:
result.add d
func isCalmoNumber(n: Positive): bool =
let d = n.divisors
if d.len == 0 or d.len mod 3 != 0:
return false
for i in countup(0, d.high, 3):
if not isPrime(d[i] + d[i + 1] + d[i + 2]):
return false
return true
for n in 1..1000:
if n.isCalmoNumber:
stdout.write ' ', n
echo()
</syntaxhighlight>
{{out}}
<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}}==
{{libheader|ntheory}}
<syntaxhighlight lang="perl" line>
use v5.36;
use ntheory<is_prime divisors>;
use List::Util 'all';
use experimental 'for_list';
sub c_divisors ($n) { my @d = divisors $n; pop @d; shift @d; @d }
for (2..1000) {
my @d = c_divisors $_;
next unless @d and 0 == @d%3;
my @sums;
for my($a,$b,$c) (@d) { push @sums, $a+$b+$c }
print "$_ " if all { is_prime $_ } @sums;
}
say '';
</syntaxhighlight>
{{out}}
<pre>
165 273 385 399 561 595 665 715 957
</pre>
=={{header|Phix}}==
Line 543 ⟶ 1,220:
{{out}}
<pre>Same as FreeBASIC entry.</pre>
=={{header|Quackery}}==
<code>factors</code> is defined at [[Factors of an integer#Quackery]].
<syntaxhighlight lang="Quackery"> [ true swap
factors dup size 3 < iff
[ drop not ] done
1 split nip
-1 split drop
dup size 3 mod 0 != iff
[ drop not ] done
[ 3 split
0 rot witheach +
factors size 2 != iff
[ dip not ] done
dup [] = until ]
drop ] is calmo ( n --> b )
[] 1000 times [ i^ calmo if [ i^ join ] ]
echo
</syntaxhighlight>
{{out}}
<pre>[ 165 273 385 399 561 595 665 715 957 ]</pre>
=={{header|Raku}}==
Line 694 ⟶ 1,397:
done...
</pre>
=={{header|RPL}}==
≪ DUP FACTORS
'''IF''' DUP SIZE 3 MOD '''THEN''' DROP2 0 '''ELSE'''
{} 1 3 PICK SIZE '''FOR''' j
OVER j GET +
2 '''STEP'''
NIP SWAP OVER / + SORT
1 CF
1 OVER SIZE '''FOR''' j
DUP j DUP 2 + SUB ∑LIST
'''IF''' ISPRIME? NOT '''THEN''' 1 SF DUP SIZE 'j' STO '''END'''
3 '''STEP''' DROP
1 FC?
'''END'''
≫ '<span style="color:blue">CALMO?</span>' STO
≪ { } 2 1000 '''FOR''' j '''IF''' j <span style="color:blue">CALMO?</span> '''THEN''' j + '''END NEXT''' ≫ '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1: { 165 273 385 399 561 595 665 715 957 }
</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 699 ⟶ 1,488:
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./seq" for Lst
import "./fmt" for Fmt
|