Calmo numbers: Difference between revisions
Added AppleScript. |
Added C |
||
Line 297:
{{out}}
<pre>Same as FreeBASIC entry.</pre>
=={{header|C}}==
{{trans|Go}}
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define LIMIT 1000
bool isPrime(int n) {
if (n < 2) return false;
if (n%2 == 0) return n == 2;
if (n%3 == 0) return n == 3;
int d = 5;
while (d*d <= n) {
if (n%d == 0) return false;
d += 2;
if (n%d == 0) return false;
d += 4;
}
return true;
}
int compare(const void* a, const void* b) {
int arg1 = *(const int*)a;
int arg2 = *(const int*)b;
if (arg1 < arg2) return -1;
if (arg1 > arg2) return 1;
return 0;
}
void eligibleDivisors(int n, int *divs, int *length) {
if (n < 1) {
*length = 0;
return;
}
int i, j, k = 1, c = 0;
if (n%2) k = 2;
for (i = k + 1; i*i <= n; i += k) {
if (!(n%i)) {
divs[c++] = i;
j = n / i;
if (j != i) divs[c++] = j;
}
}
if (c > 1) qsort(divs, c, sizeof(int), compare);
*length = c;
}
int main() {
int i, j, sum, edc, psc, cnc = 0;
int ed[30], ps[5];
bool isCalmo;
printf("Calmo numbers under 1,000:\n");
printf("Number Eligible divisors Partial sums\n");
printf("------------------------------------------------\n");
for (i = 2; i < LIMIT; ++i) {
eligibleDivisors(i, ed, &edc);
if (edc == 0 || edc % 3 != 0 ) continue;
isCalmo = true;
psc = 0;
for (j = 0; j < edc; j += 3) {
sum = ed[j] + ed[j+1] + ed[j+2];
if (!isPrime(sum)) {
isCalmo = false;
break;
}
ps[psc++] = sum;
}
if (isCalmo) {
printf("%3d [", i);
for (j = 0; j < edc; ++j) printf("%d, ", ed[j]);
printf("\b\b] \t\b\b\b\b[");
for (j = 0; j < psc; ++j) printf("%d, ", ps[j]);
printf("\b\b]\n");
}
}
return 0;
}</syntaxhighlight>
{{out}}
<pre>
Calmo numbers under 1,000:
Number Eligible divisors Partial sums
------------------------------------------------
165 [3, 5, 11, 15, 33, 55] [19, 103]
273 [3, 7, 13, 21, 39, 91] [23, 151]
385 [5, 7, 11, 35, 55, 77] [23, 167]
399 [3, 7, 19, 21, 57, 133] [29, 211]
561 [3, 11, 17, 33, 51, 187] [31, 271]
595 [5, 7, 17, 35, 85, 119] [29, 239]
665 [5, 7, 19, 35, 95, 133] [31, 263]
715 [5, 11, 13, 55, 65, 143] [29, 263]
957 [3, 11, 29, 33, 87, 319] [43, 439]
</pre>
=={{header|Go}}==
|
Revision as of 16:14, 16 April 2023
- Definition
Let n be a positive integer having k divisors (other than 1 and n itself) where k is exactly divisible by 3.
Add the first three eligible divisors, then the next three, and so on until the eligible divisors are exhausted. If the resulting partial sums are prime numbers, then n is called a Calmo number.
- Example
Consider n = 165.
It has 6 eligible divisors, namely [3 5 11 15 33 55].
The sum of the first three is: 3 + 5 + 11 = 19 which is a prime number.
The sum of the next three is: 15 + 33 + 55 = 103 which is also a prime number.
Hence n is a Calmo number.
- Task
Find and show here all Calmo numbers under 1000.
ALGOL 68
Note, the source of primes.incl.a68 is on Rosetta Code (see above link).
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 #
PR read "primes.incl.a68" PR # include prime utilities #
INT max number = 1 000; # 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 #
[]BOOL prime = PRIMESIEVE ( max number * 3 );
# 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 #
[ 1 : max number ]INT dsum;
[ 1 : max number ]INT dcount;
FOR i TO UPB dcount DO
dsum[ i ] := dcount[ i ] := IF prime[ i ] THEN -1 ELSE 0 FI
OD;
FOR i FROM 2 TO UPB dsum
DO FOR j FROM i + i BY i TO UPB dsum DO
# have another proper divisor #
IF dsum[ j ] >= 0 THEN
# this number is still a candidate #
dsum[ j ] +:= i;
dcount[ j ] +:= 1;
IF dcount[ j ] = 3 THEN
# the divisor count is currently 3 #
dsum[ j ] := dcount[ j ] :=
IF NOT prime[ dsum[ j ] ] THEN
# divisor sum isn't prime, ignore it in future #
-1
ELSE
# divisor sum is prime, reset the sum and count #
0
FI
FI
FI
OD
OD;
# show the numbers #
FOR i FROM 2 TO UPB dcount DO
IF dcount[ i ] = 0 THEN
# have a number #
print( ( " ", whole( i, 0 ) ) )
FI
OD;
print( ( newline ) )
END
- Output:
165 273 385 399 561 595 665 715 957
AppleScript
on properDivisors(n)
set output to {}
if (n > 1) then
set sqrt to n ^ 0.5
set limit to sqrt div 1
if (limit = sqrt) then
set end of output to limit
set limit to limit - 1
end if
repeat with i from limit to 2 by -1
if (n mod i is 0) then
set beginning of output to i
set end of output to n div i
end if
end repeat
set beginning of output to 1
end if
return output
end properDivisors
(* on isCalmo(n)
set pds to properDivisors(n)
set pdCount to (count pds)
if ((pdCount - 3) mod 3 ≠ 1) then return false
repeat with i from 2 to (pdCount - 1) by 3
if (properDivisors((pds's item i) + (pds's item (i + 1)) + (pds's item (i + 2))) ≠ {1}) then ¬
return false
end repeat
return true
end isCalmo *)
-- It turns out that every Calmo number < 5,000,000 is odd
-- and has exactly 6 "eligible" (ie. 7 proper) divisors, so:
on isCalmo(n)
if (n mod 2 = 0) then return false
set pds to properDivisors(n)
return (((count pds) = 7) and ¬
(properDivisors((pds's item 2) + (pds's item 3) + (pds's item 4)) = {1}) and ¬
(properDivisors((pds's item 5) + (pds's item 6) + (pds's end)) = {1}))
end isCalmo
on calmoNumbers(limit)
set output to {}
repeat with n from 20 to limit
if (isCalmo(n)) then set end of output to n
end repeat
return output
end calmoNumbers
return calmoNumbers(999)
- Output:
{165, 273, 385, 399, 561, 595, 665, 715, 957}
Arturo
calmo?: function [n][
f: (factors n) -- @[1 n]
unless zero? (size f) % 3 -> return false
every? f [x y z] -> prime? x+y+z
]
1..1000 | select => calmo?
| print
- Output:
165 273 385 399 561 595 665 715 957
BASIC
BASIC256
include "isprime.kbs"
for n = 1 to 1000-1
if isCalmo(n) then print n; " ";
next n
end
function isCalmo(n)
limite = sqr(n)
cont = 0: SumD = 0: SumQ = 0: k = 0: q = 0
d = 2
do
q = n/d
if n mod d = 0 then
cont += 1
SumD += d
SumQ += q
if cont = 3 then
k += 3
if not IsPrime(SumD) then return False
if not IsPrime(SumQ) then return False
cont = 0: SumD = 0: SumQ = 0
end if
end if
d += 1
until d >= limite
if cont <> 0 or k = 0 then return False
return True
end function
- Output:
Same as FreeBASIC entry.
FreeBASIC
#include "isprime.bas"
Function isCalmo(n As Integer) As Boolean
Dim As Integer limite = Sqr(n)
Dim As Integer cont = 0, SumD = 0, SumQ = 0, k = 0, q = 0, d = 2
Do
q = n/d
If (n Mod d) = 0 Then
cont += 1
SumD += d
SumQ += q
If cont = 3 Then
k += 3
If Not IsPrime(SumD) Orelse Not IsPrime(SumQ) Then Return False
cont = 0: SumD = 0: SumQ = 0
End If
End If
d += 1
Loop Until d >= limite
If cont <> 0 Or k = 0 Then Return False
Return True
End Function
For n As Integer = 1 To 1000-1
If isCalmo(n) Then Print n;
Next n
Sleep
- Output:
165 273 385 399 561 595 665 715 957
Run BASIC
for n = 1 to 1000-1
if isCalmo(n) then print n; " ";
next n
end
function isPrime(n)
if n < 2 then isPrime = 0 : goto [exit]
if n = 2 then isPrime = 1 : goto [exit]
if n mod 2 = 0 then isPrime = 0 : goto [exit]
isPrime = 1
for i = 3 to int(n^.5) step 2
if n mod i = 0 then isPrime = 0 : goto [exit]
next i
[exit]
end function
function isCalmo(n)
limite = sqr(n)
cont = 0: SumD = 0: SumQ = 0: k = 0: q = 0
d = 2
[start]
q = n/d
if n mod d = 0 then
cont = cont +1
SumD = SumD +d
SumQ = SumQ +q
if cont = 3 then
k = k + 3
if not(isPrime(SumD)) then isCalmo = 0 : goto [exit]
if not(isPrime(SumQ)) then isCalmo = 0 : goto [exit]
cont = 0: SumD = 0: SumQ = 0
end if
end if
d = d +1
if d < limite then [start]
if cont <> 0 or k = 0 then isCalmo = 0 : goto [exit]
isCalmo = 1
[exit]
end function
- Output:
Same as FreeBASIC entry.
Yabasic
import isprime
for n = 1 to 1000-1
if isCalmo(n) print n, " ";
next n
print
end
sub isCalmo(n)
local limite, cont, SumD, SumQ, k, d, q
limite = sqrt(n)
cont = 0: SumD = 0: SumQ = 0: k = 0: q = 0: d = 2
repeat
q = n/d
if mod(n, d) = 0 then
cont = cont+1
SumD = SumD+d
SumQ = SumQ+q
if cont = 3 then
k = k+3
if not isPrime(SumD) return False
if not isPrime(SumQ) return False
cont = 0: SumD = 0: SumQ = 0
fi
fi
d = d+1
until d >= limite
if cont <> 0 or k = 0 return False
return True
end sub
- Output:
Same as FreeBASIC entry.
C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define LIMIT 1000
bool isPrime(int n) {
if (n < 2) return false;
if (n%2 == 0) return n == 2;
if (n%3 == 0) return n == 3;
int d = 5;
while (d*d <= n) {
if (n%d == 0) return false;
d += 2;
if (n%d == 0) return false;
d += 4;
}
return true;
}
int compare(const void* a, const void* b) {
int arg1 = *(const int*)a;
int arg2 = *(const int*)b;
if (arg1 < arg2) return -1;
if (arg1 > arg2) return 1;
return 0;
}
void eligibleDivisors(int n, int *divs, int *length) {
if (n < 1) {
*length = 0;
return;
}
int i, j, k = 1, c = 0;
if (n%2) k = 2;
for (i = k + 1; i*i <= n; i += k) {
if (!(n%i)) {
divs[c++] = i;
j = n / i;
if (j != i) divs[c++] = j;
}
}
if (c > 1) qsort(divs, c, sizeof(int), compare);
*length = c;
}
int main() {
int i, j, sum, edc, psc, cnc = 0;
int ed[30], ps[5];
bool isCalmo;
printf("Calmo numbers under 1,000:\n");
printf("Number Eligible divisors Partial sums\n");
printf("------------------------------------------------\n");
for (i = 2; i < LIMIT; ++i) {
eligibleDivisors(i, ed, &edc);
if (edc == 0 || edc % 3 != 0 ) continue;
isCalmo = true;
psc = 0;
for (j = 0; j < edc; j += 3) {
sum = ed[j] + ed[j+1] + ed[j+2];
if (!isPrime(sum)) {
isCalmo = false;
break;
}
ps[psc++] = sum;
}
if (isCalmo) {
printf("%3d [", i);
for (j = 0; j < edc; ++j) printf("%d, ", ed[j]);
printf("\b\b] \t\b\b\b\b[");
for (j = 0; j < psc; ++j) printf("%d, ", ps[j]);
printf("\b\b]\n");
}
}
return 0;
}
- Output:
Calmo numbers under 1,000: Number Eligible divisors Partial sums ------------------------------------------------ 165 [3, 5, 11, 15, 33, 55] [19, 103] 273 [3, 7, 13, 21, 39, 91] [23, 151] 385 [5, 7, 11, 35, 55, 77] [23, 167] 399 [3, 7, 19, 21, 57, 133] [29, 211] 561 [3, 11, 17, 33, 51, 187] [31, 271] 595 [5, 7, 17, 35, 85, 119] [29, 239] 665 [5, 7, 19, 35, 95, 133] [31, 263] 715 [5, 11, 13, 55, 65, 143] [29, 263] 957 [3, 11, 29, 33, 87, 319] [43, 439]
Go
package main
import (
"fmt"
"rcu"
"strconv"
"strings"
)
func main() {
const limit = 1000
fmt.Println("Calmo numbers under 1,000:\n")
fmt.Println("Number Eligible divisors Partial sums")
fmt.Println("-------------------------------------------")
for i := 2; i < limit; i++ {
ed := rcu.ProperDivisors(i)[1:]
l := len(ed)
if l == 0 || l%3 != 0 {
continue
}
isCalmo := true
var ps []int
for j := 0; j < l; j += 3 {
sum := ed[j] + ed[j+1] + ed[j+2]
if !rcu.IsPrime(sum) {
isCalmo = false
break
}
ps = append(ps, sum)
}
if isCalmo {
eds := make([]string, len(ed))
for k, e := range ed {
eds[k] = strconv.Itoa(e)
}
seds := "[" + strings.Join(eds, " ") + "]"
fmt.Printf("%3d %-21s %v\n", i, seds, ps)
}
}
}
- Output:
Calmo numbers under 1,000: Number Eligible divisors Partial sums ------------------------------------------- 165 [3 5 11 15 33 55] [19 103] 273 [3 7 13 21 39 91] [23 151] 385 [5 7 11 35 55 77] [23 167] 399 [3 7 19 21 57 133] [29 211] 561 [3 11 17 33 51 187] [31 271] 595 [5 7 17 35 85 119] [29 239] 665 [5 7 19 35 95 133] [31 263] 715 [5 11 13 55 65 143] [29 263] 957 [3 11 29 33 87 319] [43 439]
J
If we ignore 1 and primes (see talk page):
isCalmo=: {{*/((,*)+/)1 p:}:_3+/\/:~_ _ _,~.}.}:*/@>,{1 ,&.>q:y}} ::0:"0
I.isCalmo i.1000
165 273 385 399 561 595 665 715 957
(This implementation relies on infinity not being specifically prime nor non-prime, and on treating the error case as "not a Calmo number").
Julia
using Primes
function divisors(n::Integer)::Vector{Int}
sort(vec(map(prod,Iterators.product((p.^(0:m) for (p,m) in eachfactor(n))...))))
end
function isCalmo(n)
divi = divisors(n)[begin+1:end-1]
ndiv = length(divi)
return ndiv > 0 && ndiv % 3 == 0 && all(isprime, sum(reshape(divi, (3, :)), dims = 1))
end
println(filter(isCalmo, 1:1000))
Phix
with javascript_semantics function calmo(integer n) sequence f = factors(n) integer l = length(f) if l=0 or remainder(l,3)!=0 then return false end if for i=1 to l by 3 do if not is_prime(sum(f[i..i+2])) then return false end if end for return true end function ?filter(tagset(1000),calmo)
- Output:
{165,273,385,399,561,595,665,715,957}
Python
#!/usr/bin/python
def isPrime(n):
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
def isCalmo(n):
limite = pow(n, 0.5)
cont = 0
SumD = 0
SumQ = 0
k = 0
q = 0
d = 2
while d < limite:
q = n/d
if n % d == 0:
cont += 1
SumD += d
SumQ += q
if cont == 3:
k += 3
if not isPrime(SumD):
return False
if not isPrime(SumQ):
return False
cont = 0
SumD = 0
SumQ = 0
d += 1
if cont != 0 or k == 0:
return False
return True
if __name__ == "__main__":
for n in range(1, 1000-1):
if isCalmo(n):
print(n, end=" ");
- Output:
Same as FreeBASIC entry.
Raku
use Prime::Factor;
use List::Divvy;
my $upto = 1e3;
my @found = (2..Inf).hyper.grep({
(so my @d = .&proper-divisors(:s)) &&
(@d.elems %% 3) &&
(all @d.batch(3)».sum».is-prime)
}).&upto($upto);
put "{+@found} found before $upto using sums of proper-divisors:\n" ~
@found.batch(10)».fmt("%4d").join: "\n";
@found = (2..Inf).hyper.grep({
(so my @d = .&proper-divisors(:s).&after: 1) &&
(@d.elems %% 3) &&
(all @d.batch(3)».sum».is-prime)
}).&upto($upto);
put "\n{+@found} found before $upto using sums of some bizarre\nbespoke definition for divisors:\n" ~
@found.batch(10)».fmt("%4d").join: "\n";
- Output:
85 found before 1000 using sums of proper-divisors: 8 21 27 35 39 55 57 65 77 85 111 115 125 129 155 161 185 187 201 203 205 209 221 235 237 265 291 299 305 309 319 323 327 335 341 365 371 377 381 391 413 415 437 451 485 489 493 497 505 515 517 535 579 611 623 649 655 667 669 671 687 689 697 707 731 737 755 767 779 781 785 831 835 851 865 893 899 901 917 921 939 955 965 979 989 9 found before 1000 using sums of some bizarre bespoke definition for divisors: 165 273 385 399 561 595 665 715 957
Ring
see "works..." + nl
numCalmo = 0
limit = 1000
for n = 1 to limit
Calmo = []
for m = 2 to n/2
if n % m = 0
add(Calmo,m)
ok
next
flag = 1
lenCalmo = len(Calmo)
if (lenCalmo > 5) and (lenCalmo % 3 = 0)
for p = 1 to lenCalmo - 2 step 3
sum = Calmo[p] + Calmo[p+1] + Calmo[p+2]
if not isPrime(sum)
flag = 0
exit
ok
next
if flag = 1
numCalmo++
see "n(" + numCalmo + ") = " + n + nl
see "divisors = ["
for p = 1 to lenCalmo - 2 step 3
sumCalmo = Calmo[p] + Calmo[p+1] + Calmo[p+2]
if not isPrime(sumCalmo)
exit
else
if p = 1
see "" + Calmo[p] + " " + Calmo[p+1] + " " + Calmo[p+2]
else
see " " + Calmo[p] + " " + Calmo[p+1] + " " + Calmo[p+2]
ok
ok
next
see "]" + nl
for p = 1 to lenCalmo - 2 step 3
sumCalmo = Calmo[p] + Calmo[p+1] + Calmo[p+2]
if isPrime(sumCalmo)
see "" + Calmo[p] + " + " + Calmo[p+1] + " + " + Calmo[p+2] + " = " + sumCalmo + " is prime" + nl
ok
next
see nl
ok
ok
next
see "Found " + numCalmo + " Calmo numbers" + nl
see "done..." + nl
func isPrime num
if (num <= 1) return 0 ok
if (num % 2 = 0 and num != 2) return 0 ok
for i = 3 to floor(num / 2) -1 step 2
if (num % i = 0) return 0 ok
next
return 1
- Output:
works... n(1) = 165 divisors = [3 5 11 15 33 55] 3 + 5 + 11 = 19 is prime 15 + 33 + 55 = 103 is prime n(2) = 273 divisors = [3 7 13 21 39 91] 3 + 7 + 13 = 23 is prime 21 + 39 + 91 = 151 is prime n(3) = 385 divisors = [5 7 11 35 55 77] 5 + 7 + 11 = 23 is prime 35 + 55 + 77 = 167 is prime n(4) = 399 divisors = [3 7 19 21 57 133] 3 + 7 + 19 = 29 is prime 21 + 57 + 133 = 211 is prime n(5) = 561 divisors = [3 11 17 33 51 187] 3 + 11 + 17 = 31 is prime 33 + 51 + 187 = 271 is prime n(6) = 595 divisors = [5 7 17 35 85 119] 5 + 7 + 17 = 29 is prime 35 + 85 + 119 = 239 is prime n(7) = 665 divisors = [5 7 19 35 95 133] 5 + 7 + 19 = 31 is prime 35 + 95 + 133 = 263 is prime n(8) = 715 divisors = [5 11 13 55 65 143] 5 + 11 + 13 = 29 is prime 55 + 65 + 143 = 263 is prime n(9) = 957 divisors = [3 11 29 33 87 319] 3 + 11 + 29 = 43 is prime 33 + 87 + 319 = 439 is prime Found 9 Calmo numbers done...
Wren
import "./math" for Int, Nums
import "./seq" for Lst
import "./fmt" for Fmt
var limit = 1000
var calmo = []
for (i in 2...limit) {
var ed = Int.properDivisors(i)
ed.removeAt(0)
if (ed.count == 0 || ed.count % 3 != 0) continue
var isCalmo = true
var ps = []
for (chunk in Lst.chunks(ed, 3)) {
var sum = Nums.sum(chunk)
if (!Int.isPrime(sum)) {
isCalmo = false
break
}
ps.add(sum)
}
if (isCalmo) calmo.add([i, ed, ps])
}
System.print("Calmo numbers under 1,000:\n")
System.print("Number Eligible divisors Partial sums")
System.print("----------------------------------------------")
for (e in calmo) {
Fmt.print("$3d $-24n $n", e[0], e[1], e[2])
}
- Output:
Calmo numbers under 1,000: Number Eligible divisors Partial sums ---------------------------------------------- 165 [3, 5, 11, 15, 33, 55] [19, 103] 273 [3, 7, 13, 21, 39, 91] [23, 151] 385 [5, 7, 11, 35, 55, 77] [23, 167] 399 [3, 7, 19, 21, 57, 133] [29, 211] 561 [3, 11, 17, 33, 51, 187] [31, 271] 595 [5, 7, 17, 35, 85, 119] [29, 239] 665 [5, 7, 19, 35, 95, 133] [31, 263] 715 [5, 11, 13, 55, 65, 143] [29, 263] 957 [3, 11, 29, 33, 87, 319] [43, 439]
XPL0
func IsPrime(N); \Return 'true' if N is prime
int N, I;
[if N <= 2 then return N = 2;
if (N&1) = 0 then \even >2\ return false;
for I:= 3 to sqrt(N) do
[if rem(N/I) = 0 then return false;
I:= I+1;
];
return true;
];
func IsCalmo(N); \Return 'true' if N is a Calmo number
int N, Limit, Count, SumD, SumQ, K, D, Q;
[Limit:= sqrt(N);
Count:= 0; SumD:= 0; SumQ:= 0; K:= 0;
D:= 2;
repeat Q:= N/D;
if rem(0) = 0 then
[Count:= Count+1;
SumD:= SumD+D;
SumQ:= SumQ+Q;
if Count = 3 then
[K:= K+3;
if not IsPrime(SumD) then return false;
if not IsPrime(SumQ) then return false;
Count:= 0; SumD:= 0; SumQ:= 0;
];
];
D:= D+1;
until D >= Limit;
if Count # 0 or K = 0 then return false;
return true;
];
int N;
[for N:= 1 to 1000-1 do
if IsCalmo(N) then
[IntOut(0, N); ChOut(0, ^ )];
]
- Output:
165 273 385 399 561 595 665 715 957