Primes - allocate descendants to their ancestors: Difference between revisions
Primes - allocate descendants to their ancestors (view source)
Revision as of 16:00, 28 January 2024
, 3 months ago→{{header|Wren}}: Minor tidy
(Added Java Solution) |
m (→{{header|Wren}}: Minor tidy) |
||
(34 intermediate revisions by 10 users not shown) | |||
Line 45:
Total Descendants 546.986
</pre>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">V maxsum = 99
F get_primes(max)
V lprimes = [2]
L(x) (3..max).step(2)
L(p) lprimes
I x % p == 0
L.break
L.was_no_break
lprimes.append(x)
R lprimes
V descendants = [[Int64]()] * (maxsum + 1)
V ancestors = [[Int64]()] * (maxsum + 1)
V primes = get_primes(maxsum)
L(p) primes
descendants[p].append(p)
L(s) 1 .< descendants.len - p
descendants[s + p] [+]= descendants[s].map(pr -> @p * pr)
L(p) primes [+] [4]
descendants[p].pop()
V total = 0
L(s) 1..maxsum
descendants[s].sort()
L(d) descendants[s]
I d > maxsum
L.break
ancestors[Int(d)] = ancestors[s] [+] [Int64(s)]
print([s]‘ Level: ’ancestors[s].len)
print(‘Ancestors: ’(I !ancestors[s].empty {String(ancestors[s])} E ‘None’))
print(‘Descendants: ’(I !descendants[s].empty {String(descendants[s].len)} E ‘None’))
I !descendants[s].empty
print(descendants[s])
print()
total += descendants[s].len
print(‘Total descendants ’total)</syntaxhighlight>
=={{header|AutoHotkey}}==
Line 50 ⟶ 95:
I seem that the use of an associative array is a little bit slower than the use of a simple array combined with the 'Sort' command, even if the 'Sort' command pumps 85% of the processing time.
<syntaxhighlight lang="autohotkey">#Warn
#SingleInstance force
#NoEnv ; Recommended for performance and compatibility with future AutoHotkey releases.
Line 214 ⟶ 259:
return lPrimes
}</
=={{header|C}}==
Line 224 ⟶ 269:
The InsertChild function is replaced by the AppendChild function which appends directly the child as the new last item in the list.
<
#include <stdio.h>
#include <stdlib.h>
Line 437 ⟶ 482:
return Index;
}</
=== Optimized Approach ===
Line 445 ⟶ 490:
It is based on the same logic as the Python script.
<
#include <stdio.h>
#include <stdlib.h>
Line 687 ⟶ 732:
return Index;
}</
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <algorithm>
#include <vector>
typedef unsigned long long integer;
// returns all ancestors of n. n is not its own ancestor.
std::vector<integer> get_ancestors(const std::vector<integer>& ancestor, integer n) {
std::vector<integer> result;
for (
n = a;
a = ancestor[n];
Line 732 ⟶ 752:
}
void print_vector(const std::vector<integer>& vec) {
if (vec.empty()) {
std::cout << "none\n";
return;
Line 746 ⟶ 764:
}
bool is_prime(integer n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
for (integer p = 3; p * p <= n; p += 2) {
if (n % p == 0)
return false;
}
return true;
}
int main(int argc, char** argv) {
const size_t limit = 100;
std::vector<integer> ancestor(limit, 0);
std::vector<std::vector<integer>> descendants(limit);
for (
if (!is_prime(prime))
continue;
descendants[prime].push_back(prime);
for (size_t i = 0; i + prime < limit; ++i) {
integer s = i + prime;
for (integer n : descendants[i]) {
integer prod = n * prime;
descendants[s].push_back(prod);
Line 772 ⟶ 799:
// print the results
size_t total_descendants = 0;
for (integer i = 1; i < limit; ++i) {
std::vector<integer> ancestors(get_ancestors(ancestor, i));
std::cout << "[" << i << "] Level: " << ancestors.size() << '\n';
Line 782 ⟶ 808:
std::cout << "Descendants: ";
std::vector<integer>& desc = descendants[i];
if (!desc.empty()) {
std::sort(desc.begin(), desc.end());
if (desc[0] == i)
Line 796 ⟶ 821:
std::cout << "Total descendants: " << total_descendants << '\n';
return 0;
}</
{{out}}
Line 830 ⟶ 855:
=={{header|Go}}==
{{trans|Python}}
<
import (
Line 913 ⟶ 938:
}
fmt.Println("\nTotal descendants", total)
}</
{{out}}
Line 943 ⟶ 968:
Total descendants 546986
</pre>
=={{header|Haskell}}==
{{trans|Racket}}
<syntaxhighlight lang="haskell">{-# LANGUAGE DeriveFunctor #-}
import Data.Numbers.Primes (isPrime)
import Data.List
------------------------------------------------------------
-- memoization utilities
type Memo2 a = Memo (Memo a)
data Memo a = Node a (Memo a) (Memo a)
deriving Functor
memo :: Integral a => Memo p -> a -> p
memo (Node a l r) n
| n == 0 = a
| odd n = memo l (n `div` 2)
| otherwise = memo r (n `div` 2 - 1)
nats :: Integral a => Memo a
nats = Node 0 ((+1).(*2) <$> nats) ((*2).(+1) <$> nats)
memoize :: Integral a => (a -> b) -> (a -> b)
memoize f = memo (f <$> nats)
memoize2 :: (Integral a, Integral b) => (a -> b -> c) -> (a -> b -> c)
memoize2 f = memoize (memoize . f)
------------------------------------------------------------
partProd = memoize2 partProdM
where
partProdM x p
| p == 0 = []
| x == 0 = [1]
| x < 0 = []
| isPrime p = ((p *) <$> partProdM (x - p) p) ++
partProd x (p - 1)
| otherwise = partProd x (p - 1)
descendants = memoize descendantsM
where
descendantsM x =
if x == 4 then [] else sort (partProd x (x - 1))
ancestors = memoize ancestorsM
where
ancestorsM z = concat [ ancestors x ++ [x]
| x <- [z-1,z-2..1]
, z `elem` descendants x ]
main = do
mapM_ (putStrLn . task1) [1..15]
putStrLn (task2 46)
putStrLn (task2 99)
putStrLn task3
where
task1 n = show n ++
" ancestors:" ++ show (ancestors n) ++
" descendants:" ++ show (descendants n)
task2 n = show n ++ " has " ++
show (length (ancestors n)) ++ " ancestors, " ++
show (length (descendants n)) ++ " descendants."
task3 = "Total ancestors up to 99: " ++
show (sum $ length . ancestors <$> [1..99]) ++
"\nTotal descendants up to 99: " ++
show (sum $ length . descendants <$> [1..99])</syntaxhighlight>
<pre>λ> main
1 ancestors:[] descendants:[]
2 ancestors:[] descendants:[]
3 ancestors:[] descendants:[]
4 ancestors:[] descendants:[]
5 ancestors:[] descendants:[6]
6 ancestors:[5] descendants:[8,9]
7 ancestors:[] descendants:[10,12]
8 ancestors:[5,6] descendants:[15,16,18]
9 ancestors:[5,6] descendants:[14,20,24,27]
10 ancestors:[7] descendants:[21,25,30,32,36]
11 ancestors:[] descendants:[28,40,45,48,54]
12 ancestors:[7] descendants:[35,42,50,60,64,72,81]
13 ancestors:[] descendants:[22,56,63,75,80,90,96,108]
14 ancestors:[5,6,9] descendants:[33,49,70,84,100,120,128,135,144,162]
15 ancestors:[5,6,8] descendants:[26,44,105,112,125,126,150,160,180,192,216,243]
46 has 3 ancestors, 557 descendants.
99 has 1 ancestors, 38257 descendants.
Total ancestors up to 99: 179
Total descendants up to 99: 546986
(3.41 secs, 737,653,968 bytes)</pre>
=={{header|J}}==
Line 968 ⟶ 1,085:
===Implementation I===
<
family=:3 :0 M.
Line 1,004 ⟶ 1,121:
)
task 99</
If you want to inspect individual results, that's fairly straightforward.
Line 1,014 ⟶ 1,131:
=== Some examples ===
<
546986
level 46
Line 1,029 ⟶ 1,146:
8 6 5
#descendants 18
19</
===Implementation II===
Line 1,042 ⟶ 1,159:
Furthermore, the script produces the full report in a '.txt' file which can easily be compared with the output of some of the other languages. In Windows : <code>fc /N /L</code>
<
dd=: (<(>y{dd),y)y}dd
y getproducts"0 >:i.maxsum-y
Line 1,084 ⟶ 1,201:
file=: jpath '~user/temp/Ancestors.ijs.txt'
main 99</
=={{header|Java}}==
{{Trans|C++}}
<
import java.util.*;
public class PrimeDescendants {
public static void main(String[] args) {
try (Writer writer = new BufferedWriter(new OutputStreamWriter(System.out))) {
printPrimeDesc(writer, 100);
} catch (IOException ex) {
ex.printStackTrace();
}
}
private static void printPrimeDesc(Writer writer, int limit) throws IOException {
List<Long> primes = findPrimes(limit);
List<Long> ancestor = new ArrayList<>(limit);
List<List<Long>> descendants = new ArrayList<>(limit);
for (int i = 0; i < limit; ++i) {
ancestor.add(Long.valueOf(0));
descendants.add(new ArrayList<Long>());
}
for (Long prime : primes) {
int p = prime.intValue();
descendants.get(p).add(prime);
for (int i = 0; i +
int s = i + p;
for (Long n : descendants.get(i)) {
Long prod = n * p;
descendants.get(s).add(prod);
Line 1,136 ⟶ 1,243:
// print the results
int totalDescendants = 0;
for (int i = 1; i < limit; ++i) {
List<Long> ancestors = getAncestors(ancestor, i);
writer.write("[" + i + "] Level: " + ancestors.size() + "\n");
Line 1,146 ⟶ 1,252:
writer.write("Descendants: ");
List<Long> desc = descendants.get(i);
if (!desc.isEmpty()) {
Collections.sort(desc);
if (desc.get(0) == i)
Line 1,162 ⟶ 1,267:
// find the prime numbers up to limit
private static List<Long> findPrimes(int limit) {
boolean[] isprime = new boolean[limit];
Arrays.fill(isprime, true);
isprime[0] = isprime[1] = false;
for (int p = 2; p * p < limit; ++p) {
if (isprime[p]) {
for (int i = p * p; i < limit; i += p)
isprime[i] = false;
Line 1,176 ⟶ 1,278:
}
List<Long> primes = new ArrayList<>();
for (int p = 2; p < limit; ++p) {
if (isprime[p])
primes.add(Long.valueOf(p));
Line 1,185 ⟶ 1,286:
// returns all ancestors of n. n is not its own ancestor.
private static List<Long> getAncestors(List<Long> ancestor, int n) {
List<Long> result = new ArrayList<>();
for (Long a = ancestor.get(n); a != 0 && a != n; ) {
n = a.intValue();
a = ancestor.get(n);
Line 1,197 ⟶ 1,296:
}
private static void print(Writer writer, List<Long> list) throws IOException {
if (list.isEmpty()) {
writer.write("none\n");
return;
Line 1,210 ⟶ 1,307:
writer.write("\n");
}
}</
{{out}}
Line 1,241 ⟶ 1,338:
Total descendants: 546986
</pre>
=== Another version ===
<syntaxhighlight lang="java">import static java.lang.Math.sqrt;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class PrimeAncestorsDescendants {
public static void main(String[] args) {
print(100);
}
public static void print(int limit) {
print(get(limit));
}
record PAD (int limit, List<List<Integer>> ancestors, List<List<Long>> descendants, int totalDescendants) {}
public static PAD get(int limit) {
List<List<Integer>> ancestors = new ArrayList<>(limit);
List<List<Long>> descendants = new ArrayList<>(limit);
for (int i=0; i<limit; i+=1) {
ancestors.add(new ArrayList<>());
descendants.add(new ArrayList<>());
}
List<Integer> primes = primesBelow(limit);
for (int p: primes) {
descendants.get(p).add((long) p);
for (int i=0, s=p; s<limit; s+=1, i+=1) {
for (long d: descendants.get(i)) {
descendants.get(s).add(p*d);
}
}
}
descendants.get(4).remove(0);
for (int p: primes) removeLast(descendants.get(p));
int totalDescendants = 0;
for (int i=1; i<limit; i+=1) {
List<Long> desc = sort(descendants.get(i));
totalDescendants += desc.size();
for (long d: desc) {
if (d >= limit) break;
ancestors.set((int) d, add(ancestors.get(i), i));
}
}
return new PAD(limit, ancestors, descendants, totalDescendants);
}
private static List<Integer> primesBelow(int limit) {
List<Integer> primes = new ArrayList<>();
boolean[] isComposite = new boolean[limit];
//int p=2; for (; p*p<limit; p+=1) {
int p=2; for (int sr=(int) sqrt(limit); p<sr; p+=1) {
if (isComposite[p]) continue;
primes.add(p);
for (int i=p*p; i<limit; i+=p) isComposite[i] = true;
}
for (; p<limit; p+=1) {
if (isComposite[p]) continue;
primes.add(p);
}
return primes;
}
private static List<Long> removeLast(List<Long> list) {
int size = list.size();
if (size > 0) list.remove(size-1);
return list;
}
private static <T extends Comparable<? super T>> List<T> sort(List<T> list) {
Collections.sort(list);
return list;
}
private static List<Integer> add(List<Integer> list, int n) {
list = new ArrayList<>(list);
list.add(n);
return list;
}
public static void print(PAD pad) {
for (int i=1; i<pad.limit; i+=1) {
if (i > 20 && i != 46 && i != 74 && i != 94 && i != 99) continue;
System.out.printf("%2d:", i);
printf(" %,d ancestors %-17s", pad.ancestors.get(i));
printf(" %,6d descendants %s\n", pad.descendants.get(i));
}
System.out.printf("\nTotal descendants: %,d\n", pad.totalDescendants);
}
private static <T extends Number> void printf(String fmt, List<T> list) {
System.out.printf(fmt, list.size(), format(list));
}
private static <T extends Number> String format(List<T> list) {
if (list.isEmpty()) return "";
StringBuilder sb = new StringBuilder("[");
if (list.size() <= 10) {
for (int i=0; i<list.size(); i+=1) sb.append(format(list, i));
}
else {
for (int i=0; i<5; i+=1) sb.append(format(list, i));
sb.append(", ...");
for (int i=list.size()-3; i<list.size(); i+=1) sb.append(format(list, i));
}
return sb.append("]").toString();
}
private static <T extends Number> String format(List<T> list, int i) {
return (i==0 ? "" : ", ") + String.format("%,d", list.get(i).longValue());
}
}
</syntaxhighlight>
{{out}}
<pre>
1: 0 ancestors 0 descendants
2: 0 ancestors 0 descendants
3: 0 ancestors 0 descendants
4: 0 ancestors 0 descendants
5: 0 ancestors 1 descendants [6]
6: 1 ancestors [5] 2 descendants [8, 9]
7: 0 ancestors 2 descendants [10, 12]
8: 2 ancestors [5, 6] 3 descendants [15, 16, 18]
9: 2 ancestors [5, 6] 4 descendants [14, 20, 24, 27]
10: 1 ancestors [7] 5 descendants [21, 25, 30, 32, 36]
11: 0 ancestors 5 descendants [28, 40, 45, 48, 54]
12: 1 ancestors [7] 7 descendants [35, 42, 50, 60, 64, 72, 81]
13: 0 ancestors 8 descendants [22, 56, 63, 75, 80, 90, 96, 108]
14: 3 ancestors [5, 6, 9] 10 descendants [33, 49, 70, 84, 100, 120, 128, 135, 144, 162]
15: 3 ancestors [5, 6, 8] 12 descendants [26, 44, 105, 112, 125, ..., 192, 216, 243]
16: 3 ancestors [5, 6, 8] 14 descendants [39, 55, 66, 98, 140, ..., 270, 288, 324]
17: 0 ancestors 16 descendants [52, 88, 99, 147, 175, ..., 405, 432, 486]
18: 3 ancestors [5, 6, 8] 19 descendants [65, 77, 78, 110, 132, ..., 576, 648, 729]
19: 0 ancestors 22 descendants [34, 104, 117, 165, 176, ..., 810, 864, 972]
20: 3 ancestors [5, 6, 9] 26 descendants [51, 91, 130, 154, 156, ..., 1.215, 1.296, 1.458]
46: 3 ancestors [7, 10, 25] 557 descendants [129, 205, 246, 493, 518, ..., 15.943.230, 17.006.112, 19.131.876]
74: 5 ancestors [5, 6, 8, 16, 39] 6.336 descendants [213, 469, 670, 793, 804, ..., 470.715.894.135, 502.096.953.744, 564.859.072.962]
94: 5 ancestors [5, 6, 9, 14, 49] 27.251 descendants [445, 534, 913, 1.633, 2.054, ..., 686.303.773.648.830, 732.057.358.558.752, 823.564.528.378.596]
99: 1 ancestors [17] 38.257 descendants [194, 1.869, 2.225, 2.670, 2.848, ..., 4.392.344.151.352.512, 4.941.387.170.271.576, 5.559.060.566.555.523]
Total descendants: 546.986
</pre>
=={{header|jq}}==
''Adapted from [[#Wren|Wren]]''
'''Works with jq and gojq, the C and Go implementations of jq'''
jaq, the Rust implementation of jq, does not currently have a `sqrt` function or support string
interpolation, but if the necessary tweaks are made, then the
following program will also run under jaq, with the same output.
<syntaxhighlight lang=jq>
def lpad($len): tostring | ($len - length) as $l | ([range(0;$l)|" "]|join("")) + .;
# Input: a positive integer
# Output: an array, $a, of length .+1 such that
# $a[$i] is $i if $i is prime, and false otherwise.
def primeSieve:
# erase(i) sets .[i*j] to false for integral j > 1
def erase($i):
if .[$i] then
reduce (range(2*$i; length; $i)) as $j (.; .[$j] = false)
else .
end;
(. + 1) as $n
| (($n|sqrt) / 2) as $s
| [null, null, range(2; $n)]
| reduce (2, 1 + (2 * range(1; $s|floor))) as $i (.; erase($i)) ;
def primes: primeSieve | map(select(.));
# Input: an array
def ellipsis($n):
if length <= $n then tostring
else "[" + (.[0:10] | map(tostring) | join(",")) + ", ...]"
end;
def task($maxSum):
($maxSum|primes) as $primes
| {maxSum: $maxSum,
descendants: [range(0; 1+$maxSum)|[]]}
| .ancestors = .descendants
| reduce $primes[] as $p (.;
.descendants[$p] += [$p]
| reduce range(1; .descendants|length - $p) as $s (.;
.descendants[$s + $p] += (.descendants[$s] | map($p * .) ) ) )
| reduce ($primes + [4])[] as $p (.; .descendants[$p] |= .[:-1] )
| .total = 0
| foreach (range(1; 1 + .maxSum),null) as $s (.;
if $s == null then .emit= "\nTotal descendants \(.total)"
else .emit = null
| .descendants[$s] |= sort
| .total += (.descendants[$s]|length)
| .ix=0
| (.descendants[$s]|length) as $ld
| until( .ix == $ld;
.descendants[$s][.ix] as $d
| if $d > .maxSum then .ix = $ld # early exit
else .ancestors[$d] = .ancestors[$s] + [$s]
| .ix += 1
end )
| if ($s < 21 or $s == 46 or $s == 74 or $s == .maxSum)
then .emit = "\($s|lpad(2)): \(.ancestors[$s]|length) ancestor[s]: \(.ancestors[$s]|lpad(18))"
| (.descendants[$s]|length) as $count
| .emit += " \($count|lpad(5)) descendant[s]: \(.descendants[$s]|ellipsis(10))"
else .
end
end)
| select(.emit).emit;
task(99)
</syntaxhighlight>
{{output}}
<pre>
1: 0 ancestor[s]: [] 0 descendant[s]: []
2: 0 ancestor[s]: [] 0 descendant[s]: []
3: 0 ancestor[s]: [] 0 descendant[s]: []
4: 0 ancestor[s]: [] 0 descendant[s]: []
5: 0 ancestor[s]: [] 1 descendant[s]: [6]
6: 1 ancestor[s]: [5] 2 descendant[s]: [8,9]
7: 0 ancestor[s]: [] 2 descendant[s]: [10,12]
8: 2 ancestor[s]: [5,6] 3 descendant[s]: [15,16,18]
9: 2 ancestor[s]: [5,6] 4 descendant[s]: [14,20,24,27]
10: 1 ancestor[s]: [7] 5 descendant[s]: [21,25,30,32,36]
11: 0 ancestor[s]: [] 5 descendant[s]: [28,40,45,48,54]
12: 1 ancestor[s]: [7] 7 descendant[s]: [35,42,50,60,64,72,81]
13: 0 ancestor[s]: [] 8 descendant[s]: [22,56,63,75,80,90,96,108]
14: 3 ancestor[s]: [5,6,9] 10 descendant[s]: [33,49,70,84,100,120,128,135,144,162]
15: 3 ancestor[s]: [5,6,8] 12 descendant[s]: [26,44,105,112,125,126,150,160,180,192, ...]
16: 3 ancestor[s]: [5,6,8] 14 descendant[s]: [39,55,66,98,140,168,189,200,225,240, ...]
17: 0 ancestor[s]: [] 16 descendant[s]: [52,88,99,147,175,210,224,250,252,300, ...]
18: 3 ancestor[s]: [5,6,8] 19 descendant[s]: [65,77,78,110,132,196,280,315,336,375, ...]
19: 0 ancestor[s]: [] 22 descendant[s]: [34,104,117,165,176,198,245,294,350,420, ...]
20: 3 ancestor[s]: [5,6,9] 26 descendant[s]: [51,91,130,154,156,220,264,297,392,441, ...]
46: 3 ancestor[s]: [7,10,25] 557 descendant[s]: [129,205,246,493,518,529,740,806,888,999, ...]
74: 5 ancestor[s]: [5,6,8,16,39] 6336 descendant[s]: [213,469,670,793,804,1333,1342,1369,1534,2014, ...]
99: 1 ancestor[s]: [17] 38257 descendant[s]: [194,1869,2225,2670,2848,3204,3237,4029,4565,5037, ...]
Total descendants 546986
</pre>
=={{header|Julia}}==
{{trans|Go}}
<
function ancestraldecendants(maxsum)
Line 1,275 ⟶ 1,620:
ancestraldecendants(99)
</syntaxhighlight>
{{output}}
<pre>
1: 0 Ancestor(s):Int64[] 0 Descendant(s): Int64[]
2: 0 Ancestor(s):Int64[] 0 Descendant(s): Int64[]
Line 1,300 ⟶ 1,647:
99: 0 Ancestor(s):Int64[] 38257 Descendant(s): [194, 1869, 2225, 2670, 2848, 3204, 3237, 4029, 4565, 5037, ...]
Total descendants: 546986
</pre>
=== A remake ===
<syntaxhighlight lang="julia">using Primes
using Printf
function primeAncestorsDecendants(maxsum)
aprimes = primes(maxsum)
ancestors = [Vector{Int}() for _ in 1:maxsum]
descendants = [Vector{Int}() for _ in 1:maxsum]
for p in aprimes
push!(descendants[p], p)
foreach(
s -> append!(descendants[s + p], [p * pr for pr in descendants[s]]),
2 : length(descendants)-p
)
end
foreach(p -> pop!(descendants[p]), [aprimes..., 4])
total = 0
format(v::Vector{Int}) = join([dot(n) for n in v], ", ")
dot(n::Int) = replace(string(n), r"(?<=[0-9])(?=(?:[0-9]{3})+(?![0-9]))" => ".")
for s in 1:maxsum
ance = [ancestors[s]..., s]
desc = sort!(descendants[s]); total += dlen = length(desc)
foreach(d-> ancestors[d] = ance,
desc[1:(i-> i==nothing ? 0 : i)(findlast(e-> e<=maxsum, desc))]
)
(s in [0:20..., 46, 74, 99]) || continue
ance = ancestors[s]; alen = length(ance)
@printf("%3d: %1d ancestors %-17s %6s descendants %s\n"
, s
, alen, alen==0 ? "" : ance
, dot(dlen), dlen==0 ? ""
: dlen<11 ? desc
: "[$(format(desc[1:5])), ..., $(format(desc[end-2:end]))]"
)
end
print("\nTotal descendants: ", total)
end
primeAncestorsDecendants(99)</syntaxhighlight>
{{output}}
<pre>
1: 0 ancestors 0 descendants
2: 0 ancestors 0 descendants
3: 0 ancestors 0 descendants
4: 0 ancestors 0 descendants
5: 0 ancestors 1 descendants [6]
6: 1 ancestors [5] 2 descendants [8, 9]
7: 0 ancestors 2 descendants [10, 12]
8: 2 ancestors [5, 6] 3 descendants [15, 16, 18]
9: 2 ancestors [5, 6] 4 descendants [14, 20, 24, 27]
10: 1 ancestors [7] 5 descendants [21, 25, 30, 32, 36]
11: 0 ancestors 5 descendants [28, 40, 45, 48, 54]
12: 1 ancestors [7] 7 descendants [35, 42, 50, 60, 64, 72, 81]
13: 0 ancestors 8 descendants [22, 56, 63, 75, 80, 90, 96, 108]
14: 3 ancestors [5, 6, 9] 10 descendants [33, 49, 70, 84, 100, 120, 128, 135, 144, 162]
15: 3 ancestors [5, 6, 8] 12 descendants [26, 44, 105, 112, 125, ..., 192, 216, 243]
16: 3 ancestors [5, 6, 8] 14 descendants [39, 55, 66, 98, 140, ..., 270, 288, 324]
17: 0 ancestors 16 descendants [52, 88, 99, 147, 175, ..., 405, 432, 486]
18: 3 ancestors [5, 6, 8] 19 descendants [65, 77, 78, 110, 132, ..., 576, 648, 729]
19: 0 ancestors 22 descendants [34, 104, 117, 165, 176, ..., 810, 864, 972]
20: 3 ancestors [5, 6, 9] 26 descendants [51, 91, 130, 154, 156, ..., 1.215, 1.296, 1.458]
46: 3 ancestors [7, 10, 25] 557 descendants [129, 205, 246, 493, 518, ..., 15.943.230, 17.006.112, 19.131.876]
74: 5 ancestors [5, 6, 8, 16, 39] 6.336 descendants [213, 469, 670, 793, 804, ..., 470.715.894.135, 502.096.953.744, 564.859.072.962]
99: 1 ancestors [17] 38.257 descendants [194, 1.869, 2.225, 2.670, 2.848, ..., 4.392.344.151.352.512, 4.941.387.170.271.576, 5.559.060.566.555.523]
Total descendants: 546.986
</pre>
=={{header|Kotlin}}==
{{trans|Python}}
<
const val MAXSUM = 99
Line 1,348 ⟶ 1,762:
println("\nTotal descendants $total")
}</
{{out}}
Line 1,378 ⟶ 1,792:
Total descendants 546986
</pre>
=={{header|Nim}}==
{{trans|Python}}
<syntaxhighlight lang="nim">import algorithm, strformat, strutils, sugar
const MaxSum = 99
func getPrimes(max: Positive): seq[int] =
if max < 2: return
result.add 2
for n in countup(3, max, 2):
block check:
for p in result:
if n mod p == 0:
break check
result.add n
let primes = getPrimes(MaxSum)
var descendants, ancestors = newSeq[seq[int]](MaxSum + 1)
for p in primes:
descendants[p].add p
for s in 1..(descendants.high - p):
descendants[s + p].add collect(newSeq, for pr in descendants[s]: p * pr)
for p in primes & 4:
discard descendants[p].pop()
var total = 0
for s in 1..MaxSum:
descendants[s].sort()
for d in descendants[s]:
if d > MaxSum: break
ancestors[d] = ancestors[s] & s
let dlength = descendants[s].len
echo &"[{s}] Level: {ancestors[s].len}"
echo "Ancestors: ", if ancestors[s].len != 0: ancestors[s].join(" ") else: "None"
echo "Descendants: ", if dlength != 0: $dlength else: "None"
if dlength != 0: echo descendants[s].join(", ")
echo ""
inc total, dlength
echo "Total descendants: ", total</syntaxhighlight>
{{out}}
<pre>[1] Level: 0
Ancestors: None
Descendants: None
..........
[10] Level: 1
Ancestors: 7
Descendants: 5
21, 25, 30, 32, 36
[11] Level: 0
Ancestors: None
Descendants: 5
28, 40, 45, 48, 54
[12] Level: 1
Ancestors: 7
Descendants: 7
35, 42, 50, 60, 64, 72, 81
[13] Level: 0
Ancestors: None
Descendants: 8
22, 56, 63, 75, 80, 90, 96, 108
..........
[46] Level: 3
Ancestors: 7 10 25
Descendants: 557
129, 205, 246, 493, 518, ..., 14171760, 15116544, 15943230, 17006112, 19131876
..........
[99] Level: 1
Ancestors: 17
Descendants: 38257
194, 1869, 2225, 2670, 2848, ..., 3904305912313344, 4117822641892980, 4392344151352512, 4941387170271576, 5559060566555523
Total descendants: 546986</pre>
=={{header|Perl}}==
{{trans|
{{libheader|ntheory}}
<
use ntheory qw(nth_prime);
Line 1,426 ⟶ 1,924:
map { for my $k (keys %{$tree{$_}{descendants}}) { $total += $tree{$_}{descendants}{$k} } } 1..$max;
print "\nTotal descendants: $total\n";</
{{out}}
<pre> 1, 0 Ancestors: [], 0 Descendants: []
Line 1,444 ⟶ 1,942:
15, 3 Ancestors: [5 6 8], 12 Descendants: [26 44 105 112 125 ... 160 180 192 216 243]
46, 3 Ancestors: [7 10 25], 557 Descendants: [129 205 246 493 518 ... 14171760 15116544 15943230 17006112 19131876]
99, 1 Ancestors: [17], 38257 Descendants: [194 1869 2225 2670 2848 ... 3904305912313344 4117822641892980 4392344151352512 4941387170271576 5559060566555523]
Line 1,520 ⟶ 1,948:
=={{header|Phix}}==
{{trans|Go}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">maxSum</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">99</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">stringify</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">descendants</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({},</span><span style="color: #000000;">maxSum</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">ancestors</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({},</span><span style="color: #000000;">maxSum</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">maxSum</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">descendants</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">descendants</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">descendants</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">p</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">descendants</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">+</span><span style="color: #000000;">p</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">descendants</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">+</span><span style="color: #000000;">p</span><span style="color: #0000FF;">])</span>
<span style="color: #0000FF;">&</span> <span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">descendants</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span>
<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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">descendants</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">])!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">descendants</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">descendants</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</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;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">total</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">maxSum</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">descendants</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">]))</span>
<span style="color: #000000;">total</span> <span style="color: #0000FF;">+=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">></span><span style="color: #000000;">maxSum</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">ancestors</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ancestors</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">])</span>
<span style="color: #0000FF;">&</span><span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ancestors</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">]),</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;"><</span><span style="color: #000000;">26</span> <span style="color: #008080;">or</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">46</span><span style="color: #0000FF;">,</span><span style="color: #000000;">74</span><span style="color: #0000FF;">,</span><span style="color: #000000;">99</span><span style="color: #0000FF;">})</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ancestors</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">sp</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"s"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stringify</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</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;">"%2d: %d Ancestor%s: [%-14s"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sp</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"]"</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">descendants</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">]))</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">sp</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"s"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;"><</span><span style="color: #000000;">10</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stringify</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stringify</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"..."</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;">"%5d Descendant%s: [%s]\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sp</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</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;">"\nTotal descendants %d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">total</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- about 1s</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">33</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">4e9</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- over 16 days</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,635 ⟶ 2,052:
Total descendants 546986
"
"16 days, 2 hours, 2 minutes and 45s"
</pre>
Line 1,644 ⟶ 2,061:
=={{header|Python}}==
Python is very flexible, concise and effective with lists.
<
from itertools import takewhile
Line 1,687 ⟶ 2,104:
total += len(descendants[s])
print("Total descendants", total)</
=={{header|Racket}}==
Line 1,699 ⟶ 2,116:
We first define a macro to create memorized functions and a few auxiliary functions. In particular <code>(border list)</code> transforms a long list in a list with ellipsis.
<
(define-syntax-rule (define/mem (name args ...) body ...)
Line 1,716 ⟶ 2,133:
(define (add-tail list x)
(reverse (cons x (reverse list))))</
The main part of the program uses the memorized functions.
<
(if (= x 1)
#f
Line 1,762 ⟶ 2,179:
(define (total-descendants n)
(for/sum ([x (in-range 1 (add1 n))])
(length (descendants x))))</
Now we display some results.
<
(show-info x))
(for ([x (in-range 1 (add1 15))])
Line 1,778 ⟶ 2,195:
(newline)
(printf "Total ancestors up to 99: ~a\n" (total-ancestors 99))
(printf "Total descendants up to 99: ~a\n" (total-descendants 99))</
{{out}}
Line 1,804 ⟶ 2,221:
Total ancestors up to 99: 179
Total descendants up to 99: 546986</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2018.11}}
<syntaxhighlight lang="raku" line>my $max = 99;
my @primes = (2 .. $max).grep: *.is-prime;
my %tree;
(1..$max).map: {
%tree{$_}<ancestor> = ();
%tree{$_}<descendants> = {};
};
sub allocate ($n, $i = 0, $sum = 0, $prod = 1) {
return if $n < 4;
for @primes.kv -> $k, $p {
next if $k < $i;
if ($sum + $p) <= $n {
allocate($n, $k, $sum + $p, $prod * $p);
} else {
last if $sum == $prod;
%tree{$sum}<descendants>{$prod} = True;
last if $prod > $max;
%tree{$prod}<ancestor> = %tree{$sum}<ancestor> (|) $sum;
last;
}
}
}
# abbreviate long lists to first and last 5 elements
sub abbrev (@d) { @d < 11 ?? @d !! ( @d.head(5), '...', @d.tail(5) ) }
my @print = flat 1 .. 15, 46, 74, $max;
(1 .. $max).map: -> $term {
allocate($term);
if $term == any( @print ) # print some representative lines
{
my $dn = +%tree{$term}<descendants> // 0;
my $dl = abbrev(%tree{$term}<descendants>.keys.sort( +*) // ());
printf "%2d, %2d Ancestors: %-14s %5d Descendants: %s\n",
$term, %tree{$term}<ancestor>,
"[{ %tree{$term}<ancestor>.keys.sort: +* }],", $dn, "[$dl]";
}
}
say "\nTotal descendants: ",
sum (1..$max).map({ +%tree{$_}<descendants> });</syntaxhighlight>
{{out}}
<pre> 1, 0 Ancestors: [], 0 Descendants: []
2, 0 Ancestors: [], 0 Descendants: []
3, 0 Ancestors: [], 0 Descendants: []
4, 0 Ancestors: [], 0 Descendants: []
5, 0 Ancestors: [], 1 Descendants: [6]
6, 1 Ancestors: [5], 2 Descendants: [8 9]
7, 0 Ancestors: [], 2 Descendants: [10 12]
8, 2 Ancestors: [5 6], 3 Descendants: [15 16 18]
9, 2 Ancestors: [5 6], 4 Descendants: [14 20 24 27]
10, 1 Ancestors: [7], 5 Descendants: [21 25 30 32 36]
11, 0 Ancestors: [], 5 Descendants: [28 40 45 48 54]
12, 1 Ancestors: [7], 7 Descendants: [35 42 50 60 64 72 81]
13, 0 Ancestors: [], 8 Descendants: [22 56 63 75 80 90 96 108]
14, 3 Ancestors: [5 6 9], 10 Descendants: [33 49 70 84 100 120 128 135 144 162]
15, 3 Ancestors: [5 6 8], 12 Descendants: [26 44 105 112 125 ... 160 180 192 216 243]
46, 3 Ancestors: [7 10 25], 557 Descendants: [129 205 246 493 518 ... 14171760 15116544 15943230 17006112 19131876]
74, 5 Ancestors: [5 6 8 16 39], 6336 Descendants: [213 469 670 793 804 ... 418414128120 446308403328 470715894135 502096953744 564859072962]
99, 1 Ancestors: [17], 38257 Descendants: [194 1869 2225 2670 2848 ... 3904305912313344 4117822641892980 4392344151352512 4941387170271576 5559060566555523]
Total descendants: 546986</pre>
=={{header|Sidef}}==
{{trans|Go}}
<
var primes = maxsum.primes
Line 1,832 ⟶ 2,321:
var idx = descendants[s].first_index {|x| x > maxsum }
for d in (descendants[s].
ancestors[d] = (ancestors[s] + [s])
}
Line 1,843 ⟶ 2,332:
}
say "\nTotal descendants: #{total}"</
{{out}}
<pre>
Line 1,875 ⟶ 2,364:
=={{header|Simula}}==
{{trans|Python}}
<
BEGIN
Line 2,164 ⟶ 2,653:
OUTINT(TOTAL, 0);
OUTIMAGE;
END.</
{{out}}
<pre>[1] LEVEL: 0
Line 2,268 ⟶ 2,757:
=={{header|Visual Basic .NET}}==
It is based on the same logic as the Python script.
<
Module Module1
Line 2,485 ⟶ 2,974:
Return vbTrue
End Function
End Module</
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-math}}
{{libheader|Wren-sort}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./math" for Int
import "./sort" for Sort
import "./fmt" for Fmt
var maxSum = 99
var descendants = List.filled(maxSum + 1, null)
var ancestors = List.filled(maxSum + 1, null)
for (i in 0..maxSum) {
descendants[i] = []
ancestors[i] = []
}
var primes = Int.primeSieve(maxSum)
for (p in primes) {
descendants[p].add(p)
for (s in 1...descendants.count - p) {
descendants[s + p].addAll(descendants[s].map { |d| p * d })
}
}
for (p in primes + [4]) descendants[p].removeAt(-1)
var total = 0
for (s in 1..maxSum) {
Sort.quick(descendants[s])
total = total + descendants[s].count
for (d in descendants[s]) {
if (d > maxSum) break
ancestors[d] = ancestors[s] + [s]
}
if (s < 21 || s == 46 || s == 74 || s == maxSum) {
Fmt.write("$2d: $d Ancestors[s]: $-18n", s, ancestors[s].count, ancestors[s])
var count = descendants[s].count
var desc10 = (count <= 10) ? descendants[s] : descendants[s].take(10).toList + ["..."]
Fmt.print("$5d Descendants[s]: $n", count, desc10)
}
}
System.print("\nTotal descendants %(total)")</syntaxhighlight>
{{out}}
<pre>
1: 0 Ancestors[s]: [] 0 Descendants[s]: []
2: 0 Ancestors[s]: [] 0 Descendants[s]: []
3: 0 Ancestors[s]: [] 0 Descendants[s]: []
4: 0 Ancestors[s]: [] 0 Descendants[s]: []
5: 0 Ancestors[s]: [] 1 Descendants[s]: [6]
6: 1 Ancestors[s]: [5] 2 Descendants[s]: [8, 9]
7: 0 Ancestors[s]: [] 2 Descendants[s]: [10, 12]
8: 2 Ancestors[s]: [5, 6] 3 Descendants[s]: [15, 16, 18]
9: 2 Ancestors[s]: [5, 6] 4 Descendants[s]: [14, 20, 24, 27]
10: 1 Ancestors[s]: [7] 5 Descendants[s]: [21, 25, 30, 32, 36]
11: 0 Ancestors[s]: [] 5 Descendants[s]: [28, 40, 45, 48, 54]
12: 1 Ancestors[s]: [7] 7 Descendants[s]: [35, 42, 50, 60, 64, 72, 81]
13: 0 Ancestors[s]: [] 8 Descendants[s]: [22, 56, 63, 75, 80, 90, 96, 108]
14: 3 Ancestors[s]: [5, 6, 9] 10 Descendants[s]: [33, 49, 70, 84, 100, 120, 128, 135, 144, 162]
15: 3 Ancestors[s]: [5, 6, 8] 12 Descendants[s]: [26, 44, 105, 112, 125, 126, 150, 160, 180, 192, ...]
16: 3 Ancestors[s]: [5, 6, 8] 14 Descendants[s]: [39, 55, 66, 98, 140, 168, 189, 200, 225, 240, ...]
17: 0 Ancestors[s]: [] 16 Descendants[s]: [52, 88, 99, 147, 175, 210, 224, 250, 252, 300, ...]
18: 3 Ancestors[s]: [5, 6, 8] 19 Descendants[s]: [65, 77, 78, 110, 132, 196, 280, 315, 336, 375, ...]
19: 0 Ancestors[s]: [] 22 Descendants[s]: [34, 104, 117, 165, 176, 198, 245, 294, 350, 420, ...]
20: 3 Ancestors[s]: [5, 6, 9] 26 Descendants[s]: [51, 91, 130, 154, 156, 220, 264, 297, 392, 441, ...]
46: 3 Ancestors[s]: [7, 10, 25] 557 Descendants[s]: [129, 205, 246, 493, 518, 529, 740, 806, 888, 999, ...]
74: 5 Ancestors[s]: [5, 6, 8, 16, 39] 6336 Descendants[s]: [213, 469, 670, 793, 804, 1333, 1342, 1369, 1534, 2014, ...]
99: 1 Ancestors[s]: [17] 38257 Descendants[s]: [194, 1869, 2225, 2670, 2848, 3204, 3237, 4029, 4565, 5037, ...]
Total descendants 546986
</pre>
=={{header|zkl}}==
Line 2,491 ⟶ 3,051:
{{trans|Racket}}
Using [[Extensible prime generator#zkl]]
<
primes:=Utils.Generator(Import("sieve.zkl").postponed_sieve)
Line 2,520 ⟶ 3,080:
}
println("Total ancestors: %,d".fmt(ta));
println("Total descendants: %,d".fmt(td));</
{{out}}
<pre>
|