Ludic numbers
You are encouraged to solve this task according to the task description, using any language you may know.
Ludic numbers are related to prime numbers as they are generated by a sieve quite like the Sieve of Eratosthenes is used to generate prime numbers.
The first ludic number is 1.
To generate succeeding ludic numbers create an array of increasing integers starting from 2
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ...
(Loop)
- Take the first member of the resultant array as the next Ludic number 2.
- Remove every 2'nd indexed item from the array (including the first).
234567891011121314151617181920212223242526...
- (Unrolling a few loops...)
- Take the first member of the resultant array as the next Ludic number 3.
- Remove every 3'rd indexed item from the array (including the first).
35 7911 131517 192123 252729 313335 373941 434547 4951...
- Take the first member of the resultant array as the next Ludic number 5.
- Remove every 5'th indexed item from the array (including the first).
57 11 13 171923 25 29 313537 41 43 474953 55 59 616567 71 73 77 ...
- Take the first member of the resultant array as the next Ludic number 7.
- Remove every 7'th indexed item from the array (including the first).
711 13 17 23 25 293137 41 43 47 53 555961 67 71 73 77 838589 91 97 ...
- ...
- Take the first member of the current array as the next Ludic number L.
- Remove every L'th indexed item from the array (including the first).
- ...
- Task
- Generate and show here the first 25 ludic numbers.
- How many ludic numbers are there less than or equal to 1000?
- Show the 2000..2005'th ludic numbers.
- A triplet is any three numbers where all three numbers are also ludic numbers. Show all triplets of ludic numbers < 250 (Stretch goal)
AutoHotkey
<lang AutoHotkey>#NoEnv SetBatchLines, -1 Ludic := LudicSieve(22000)
Loop, 25 ; the first 25 ludic numbers Task1 .= Ludic[A_Index] " "
for i, Val in Ludic ; the number of ludic numbers less than or equal to 1000 if (Val <= 1000) Task2++ else break
Loop, 6 ; the 2000..2005'th ludic numbers Task3 .= Ludic[1999 + A_Index] " "
for i, Val in Ludic { ; all triplets of ludic numbers < 250 if (Val + 6 > 249) break if (Ludic[i + 1] = Val + 2 && Ludic[i + 2] = Val + 6 || i = 1) Task4 .= "(" Val " " Val + 2 " " Val + 6 ") " }
MsgBox, % "First 25:`t`t" Task1 . "`nLudics below 1000:`t" Task2 . "`nLudic 2000 to 2005:`t" Task3 . "`nTriples below 250:`t" Task4 return
LudicSieve(Limit) { Arr := [], Ludic := [] Loop, % Limit Arr.Insert(A_Index) Ludic.Insert(Arr.Remove(1)) while Arr.MaxIndex() != 1 { Ludic.Insert(n := Arr.Remove(1)) , Removed := 0 Loop, % Arr.MaxIndex() // n { Arr.Remove(A_Index * n - Removed) , Removed++ } } Ludic.Insert(Arr[1]) return Ludic }</lang>
- Output:
First 25: 1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 107 Ludics below 1000: 142 Ludic 2000 to 2005: 21475 21481 21487 21493 21503 21511 Triples below 250: (1 3 7) (5 7 11) (11 13 17) (23 25 29) (41 43 47) (173 175 179) (221 223 227) (233 235 239)
C
<lang c>#include <stdio.h>
- include <stdlib.h>
typedef unsigned uint; typedef struct { uint i, v; } filt_t;
// ludics with at least so many elements and reach at least such value uint* ludic(uint min_len, uint min_val, uint *len) { uint cap, i, v, active = 1, nf = 0; filt_t *f = calloc(cap = 2, sizeof(*f)); f[1].i = 4;
for (v = 1; ; ++v) { for (i = 1; i < active && --f[i].i; i++);
if (i < active) f[i].i = f[i].v; else if (nf == f[i].i) f[i].i = f[i].v, ++active; // enable one more filter else { if (nf >= cap) f = realloc(f, sizeof(*f) * (cap*=2)); f[nf] = (filt_t){ v + nf, v }; if (++nf >= min_len && v >= min_val) break; } }
// pack the sequence into a uint[] // filt_t struct was used earlier for cache locality in loops uint *x = (void*) f; for (i = 0; i < nf; i++) x[i] = f[i].v; x = realloc(x, sizeof(*x) * nf);
*len = nf; return x; }
int find(uint *a, uint v) { uint i; for (i = 0; a[i] <= v; i++) if (v == a[i]) return 1; return 0; }
int main(void) { uint len, i, *x = ludic(2005, 1000, &len);
printf("First 25:"); for (i = 0; i < 25; i++) printf(" %u", x[i]); putchar('\n');
for (i = 0; x[i] <= 1000; i++); printf("Ludics below 1000: %u\n", i);
printf("Ludic 2000 to 2005:"); for (i = 2000; i <= 2005; i++) printf(" %u", x[i - 1]); putchar('\n');
printf("Triples below 250:"); for (i = 0; x[i] + 6 <= 250; i++) if (find(x, x[i] + 2) && find(x, x[i] + 6)) printf(" (%u %u %u)", x[i], x[i] + 2, x[i] + 6);
putchar('\n');
free(x); return 0; }</lang>
- Output:
First 25: 1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 107 Ludics below 1000: 142 Ludic 2000 to 2005: 21475 21481 21487 21493 21503 21511 Triples below 250: (1 3 7) (5 7 11) (11 13 17) (23 25 29) (41 43 47) (173 175 179) (221 223 227) (233 235 239)
C++
<lang cpp>
- include <vector>
- include <iostream>
using namespace std;
class ludic { public:
void ludicList()
{
_list.push_back( 1 );
vector<int> v;
for( int x = 2; x < 22000; x++ )
v.push_back( x );
while( true )
{
vector<int>::iterator i = v.begin();
int z = *i;
_list.push_back( z );
while( true )
{
i = v.erase( i );
if( distance( i, v.end() ) <= z - 1 ) break;
advance( i, z - 1 );
}
if( v.size() < 1 ) return;
}
}
void show( int s, int e )
{
for( int x = s; x < e; x++ )
cout << _list[x] << " ";
}
void findTriplets( int e )
{
int lu, x = 0;
while( _list[x] < e )
{
lu = _list[x];
if( inList( lu + 2 ) && inList( lu + 6 ) )
cout << "(" << lu << " " << lu + 2 << " " << lu + 6 << ")\n";
x++;
}
}
int count( int e )
{
int x = 0, c = 0;
while( _list[x++] <= 1000 ) c++;
return c;
}
private:
bool inList( int lu )
{
for( int x = 0; x < 250; x++ )
if( _list[x] == lu ) return true;
return false;
}
vector<int> _list;
};
int main( int argc, char* argv[] ) {
ludic l; l.ludicList(); cout << "first 25 ludic numbers:" << "\n"; l.show( 0, 25 ); cout << "\n\nThere are " << l.count( 1000 ) << " ludic numbers <= 1000" << "\n"; cout << "\n2000 to 2005'th ludic numbers:" << "\n"; l.show( 1999, 2005 ); cout << "\n\nall triplets of ludic numbers < 250:" << "\n"; l.findTriplets( 250 ); cout << "\n\n"; return system( "pause" );
} </lang>
- Output:
first 25 ludic numbers: 1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 107 There are 142 ludic numbers <= 1000 2000 to 2005'th ludic numbers: 21475 21481 21487 21493 21503 21511 all triplets of ludic numbers < 250: (1 3 7) (5 7 11) (11 13 17) (23 25 29) (41 43 47) (173 175 179) (221 223 227) (233 235 239)
Clojure
<lang clojure>(defn ints-from [n]
(cons n (lazy-seq (ints-from (inc n)))))
(defn drop-nth [n seq]
(cond
(zero? n) seq
(empty? seq) []
:else (concat (take (dec n) seq) (lazy-seq (drop-nth n (drop n seq))))))
(def ludic ((fn ludic
([] (ludic 1)) ([n] (ludic n (ints-from (inc n)))) ([n [f & r]] (cons n (lazy-seq (ludic f (drop-nth f r))))))))
(defn ludic? [n] (= (first (filter (partial <= n) ludic)) n))
(print "First 25: ") (println (take 25 ludic)) (print "Count below 1000: ") (println (count (take-while (partial > 1000) ludic))) (print "2000th through 2005th: ") (println (map (partial nth ludic) (range 1999 2005))) (print "Triplets < 250: ") (println (filter (partial every? ludic?)
(for [i (range 250)] (list i (+ i 2) (+ i 6)))))</lang>
- Output:
First 25: (1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 107) Count below 1000: 142 2000th through 2005th: (21475 21481 21487 21493 21503 21511) Triplets < 250: ((1 3 7) (5 7 11) (11 13 17) (23 25 29) (41 43 47) (173 175 179) (221 223 227) (233 235 239))
D
opApply Version
<lang d>struct Ludics(T) {
int opApply(int delegate(in ref T) dg) {
int result;
T[] rotor, taken = [T(1)];
result = dg(taken[0]);
if (result) return result;
for (T i = 2; ; i++) { // Shoud be stopped if T has a max.
size_t j = 0;
for (; j < rotor.length; j++)
if (!--rotor[j])
break;
if (j < rotor.length) {
rotor[j] = taken[j + 1];
} else {
result = dg(i);
if (result) return result;
taken ~= i;
rotor ~= taken[j + 1];
}
}
}
}
void main() {
import std.stdio, std.range, std.algorithm;
// std.algorithm.take can't be used here.
uint[] L;
foreach (const x; Ludics!uint())
if (L.length < 2005)
L ~= x;
else
break;
writeln("First 25 ludic primes:\n", L.take(25));
writefln("\nThere are %d ludic numbers <= 1000.",
L.until!q{ a > 1000 }.walkLength);
writeln("\n2000'th .. 2005'th ludic primes:\n", L[1999 .. 2005]);
enum m = 250;
const triplets = L.filter!(x => x + 6 < m &&
L.canFind(x + 2) && L.canFind(x + 6))
// Ugly output:
//.map!(x => tuple(x, x + 2, x + 6)).array;
.map!(x => [x, x + 2, x + 6]).array;
writefln("\nThere are %d triplets less than %d:\n%s",
triplets.length, m, triplets);
}</lang>
- Output:
First 25 ludic primes: [1, 2, 3, 5, 7, 11, 13, 17, 23, 25, 29, 37, 41, 43, 47, 53, 61, 67, 71, 77, 83, 89, 91, 97, 107] There are 142 ludic numbers <= 1000. 2000'th .. 2005'th ludic primes: [21475, 21481, 21487, 21493, 21503, 21511] There are 8 triplets less than 250: [[1, 3, 7], [5, 7, 11], [11, 13, 17], [23, 25, 29], [41, 43, 47], [173, 175, 179], [221, 223, 227], [233, 235, 239]]
The run-time is about 0.03 seconds or less. It takes about 2.0 seconds to generate 50_000 Ludic numbers with ldc2 compiler.
Range Version
This is the same code modified to be a Range. <lang d>struct Ludics(T) {
T[] rotor, taken = [T(1)]; T i; size_t j; T front = 1; // = taken[0]; bool running = false; static immutable bool empty = false;
void popFront() pure nothrow @safe {
if (running)
goto RESUME;
else
running = true;
i = 2;
while (true) {
j = 0;
while (j < rotor.length) {
rotor[j]--;
if (!rotor[j])
break;
j++;
}
if (j < rotor.length) {
rotor[j] = taken[j + 1];
} else {
front = i;
return;
RESUME:
taken ~= i;
rotor ~= taken[j + 1];
}
i++; // Could overflow if T has a max.
}
}
}
void main() {
import std.stdio, std.range, std.algorithm, std.array;
Ludics!uint L;
writeln("First 25 ludic primes:\n", L.take(25));
writefln("\nThere are %d ludic numbers <= 1000.",
L.until!q{ a > 1000 }.walkLength);
writeln("\n2000'th .. 2005'th ludic primes:\n", L.drop(1999).take(6));
enum uint m = 250;
const few = L.until!(x => x > m).array;
const triplets = few.filter!(x => x + 6 < m && few.canFind(x + 2)
&& few.canFind(x + 6))
// Ugly output:
//.map!(x => tuple(x, x + 2, x + 6)).array;
.map!(x => [x, x + 2, x + 6]).array;
writefln("\nThere are %d triplets less than %d:\n%s",
triplets.length, m, triplets);
}</lang> The output is the same. This version is slower, it takes about 3.3 seconds to generate 50_000 Ludic numbers with ldc2 compiler.
Go
<lang go>package main
import "fmt"
// Ludic returns a slice of Ludic numbers stopping after // either n entries or when max is exceeded. // Either argument may be <=0 to disable that limit. func Ludic(n int, max int) []uint32 { const maxInt32 = 1<<31 - 1 // i.e. math.MaxInt32 if max > 0 && n < 0 { n = maxInt32 } if n < 1 { return nil } if max < 0 { max = maxInt32 } sieve := make([]uint32, 10760) // XXX big enough for 2005 Ludics sieve[0] = 1 sieve[1] = 2 if n > 2 { // We start with even numbers already removed for i, j := 2, uint32(3); i < len(sieve); i, j = i+1, j+2 { sieve[i] = j } // We leave the Ludic numbers in place, // k is the index of the next Ludic for k := 2; k < n; k++ { l := int(sieve[k]) if l >= max { n = k break } i := l l-- // last is the last valid index last := k + i - 1 for j := k + i + 1; j < len(sieve); i, j = i+1, j+1 { last = k + i sieve[last] = sieve[j] if i%l == 0 { j++ } } // Truncate down to only the valid entries if last < len(sieve)-1 { sieve = sieve[:last+1] } } } if n > len(sieve) { panic("program error") // should never happen } return sieve[:n] }
func has(x []uint32, v uint32) bool { for i := 0; i < len(x) && x[i] <= v; i++ { if x[i] == v { return true } } return false }
func main() { // Ludic() is so quick we just call it repeatedly fmt.Println("First 25:", Ludic(25, -1)) fmt.Println("Numner of Ludics below 1000:", len(Ludic(-1, 1000))) fmt.Println("Ludic 2000 to 2005:", Ludic(2005, -1)[1999:])
fmt.Print("Tripples below 250:") x := Ludic(-1, 250) for i, v := range x[:len(x)-2] { if has(x[i+1:], v+2) && has(x[i+2:], v+6) { fmt.Printf(", (%d %d %d)", v, v+2, v+6) } } fmt.Println() }</lang> Run in Go Playground.
- Output:
First 25: [1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 107] Numner of Ludics below 1000: 142 Ludic 2000 to 2005: [21475 21481 21487 21493 21503 21511] Tripples below 250:, (1 3 7), (5 7 11), (11 13 17), (23 25 29), (41 43 47), (173 175 179), (221 223 227), (233 235 239)
Haskell
<lang haskell>import Data.List (unfoldr, genericSplitAt)
ludic :: [Integer] ludic = 1 : unfoldr (\xs@(x:_) -> Just (x, dropEvery x xs)) [2..] where
dropEvery n = concat . map tail . unfoldr (Just . genericSplitAt n)
main :: IO () main = do
print $ take 25 $ ludic print $ length $ takeWhile (<= 1000) $ ludic print $ take 6 $ drop 1999 $ ludic -- haven't done triplets task yet</lang>
- Output:
[1,2,3,5,7,11,13,17,23,25,29,37,41,43,47,53,61,67,71,77,83,89,91,97,107] 142 [21475,21481,21487,21493,21503,21511]
The filter for dropping every n-th number can be delayed until it's needed, which speeds up the generator, more so when a longer sequence is taken. <lang haskell>ludic = 1:2 : f 3 [3..] [(4,2)] where f n (x:xs) yy@((i,y):ys) | n == i = f n (dropEvery y xs) ys | otherwise = x : f (1+n) xs (yy ++ [(n+x, x)])
dropEvery n s = a ++ dropEvery n (tail b) where (a,b) = splitAt (n-1) s
main = print $ ludic !! 10000</lang>
Icon and Unicon
This is inefficient, but was fun to code as a cascade of filters. Works in both languages. <lang unicon>global num, cascade, sieve, nfilter
procedure main(A)
lds := ludic(2005) # All we need for the four tasks.
every writes("First 25:" | (" "||!lds)\25 | "\n")
every (n := 0) +:= (!lds < 1000, 1)
write("There are ",n," Ludic numbers < 1000.")
every writes("2000th through 2005th: " | (lds[2000 to 20005]||" ") | "\n")
writes("Triplets:")
every (250 > (x := !lds)) & (250 > (x+2 = !lds)) & (250 > (x+6 = !lds)) do
writes(" [",x,",",x+2,",",x+6,"]")
write()
end
procedure ludic(limit)
candidates := create seq(2)
put(cascade := [], create {
repeat {
report(l := num, limit)
put(cascade, create (cnt:=0, repeat ((cnt+:=1)%l=0, @sieve) | @@nfilter))
cascade[-2] :=: cascade[-1] # keep this sink as the last filter
@sieve
}
})
sieve := create while num := @candidates do @@(nfilter := create !cascade)
report(1, limit)
return @sieve
end
procedure report(ludic, limit)
static count, lds
initial {count := 0; lds := []}
if (count +:= 1) > limit then lds@&main
put(lds, ludic)
end</lang>
Output:
->ludic First 25: 1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 107 There are 142 Ludic numbers < 1000. 2000th through 20005th: 21475 21481 21487 21493 21503 21511 Triplets: [1,3,7] [5,7,11] [11,13,17] [23,25,29] [41,43,47] [173,175,179] [221,223,227] [233,235,239] ->
J
Solution (naive / brute force):<lang j> ludic =: _1 |.!.1 [: {."1 [: (#~ 0 ~: {. | i.@#)^:a: 2 + i.</lang> Examples:<lang j> # ludic 110 NB. 110 is sufficient to generate 25 Ludic numbers 25
ludic 110 NB. First 25 Ludic numbers
1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 107
#ludic 1000 NB. 142 Ludic numbers <= 1000
142
# ludic 22000 NB. 22000 is sufficient to generate > 2005 Ludic numbers
2042
(2000+i.6) { ludic 22000 NB. Ludic numbers 2000-2005
21481 21487 21493 21503 21511 21523
0 2 6 (] (*./ .e.~ # |:@]) +/) ludic 250 NB. Ludic triplets <= 250 1 3 7 5 7 11 11 13 17 23 25 29 41 43 47
173 175 179 221 223 227 233 235 239</lang>
Java
This example uses pre-calculated ranges for the first and third task items (noted in comments). <lang java5>import java.util.ArrayList; import java.util.List;
public class Ludic{ public static List<Integer> ludicUpTo(int n){ List<Integer> ludics = new ArrayList<Integer>(n); for(int i = 1; i <= n; i++){ //fill the initial list ludics.add(i); }
//start at index 1 because the first ludic number is 1 and we don't remove anything for it for(int cursor = 1; cursor < ludics.size(); cursor++){ int thisLudic = ludics.get(cursor); //the first item in the list is a ludic number int removeCursor = cursor + thisLudic; //start removing that many items later while(removeCursor < ludics.size()){ ludics.remove(removeCursor); //remove the next item removeCursor = removeCursor + thisLudic - 1; //move the removal cursor up as many spaces as we need to //then back one to make up for the item we just removed } } return ludics; }
public static List<List<Integer>> getTriplets(List<Integer> ludics){ List<List<Integer>> triplets = new ArrayList<List<Integer>>(); for(int i = 0; i < ludics.size() - 2; i++){ //only need to check up to the third to last item int thisLudic = ludics.get(i); if(ludics.contains(thisLudic + 2) && ludics.contains(thisLudic + 6)){ List<Integer> triplet = new ArrayList<Integer>(3); triplet.add(thisLudic); triplet.add(thisLudic + 2); triplet.add(thisLudic + 6); triplets.add(triplet); } } return triplets; }
public static void main(String[] srgs){ System.out.println("First 25 Ludics: " + ludicUpTo(110)); //110 will get us 25 numbers System.out.println("Ludics up to 1000: " + ludicUpTo(1000).size()); System.out.println("2000th - 2005th Ludics: " + ludicUpTo(22000).subList(1999, 2005)); //22000 will get us 2005 numbers System.out.println("Triplets up to 250: " + getTriplets(ludicUpTo(250))); } }</lang>
- Output:
First 25 Ludics: [1, 2, 3, 5, 7, 11, 13, 17, 23, 25, 29, 37, 41, 43, 47, 53, 61, 67, 71, 77, 83, 89, 91, 97, 107] Ludics up to 1000: 142 2000th - 2005th Ludics: [21475, 21481, 21487, 21493, 21503, 21511] Triplets up to 250: [[1, 3, 7], [5, 7, 11], [11, 13, 17], [23, 25, 29], [41, 43, 47], [173, 175, 179], [221, 223, 227], [233, 235, 239]]
Mathematica
<lang Mathematica>n=10^5; Ludic={1}; seq=Range[2,n]; ClearAll[DoStep] DoStep[seq:{f_,___}]:=Module[{out=seq},
AppendTo[Ludic,f]; out;;;;f=Sequence[]; out
] Nest[DoStep,seq,2500];</lang>
- Output:
Ludic[[;; 25]]
LengthWhile[Ludic, # < 1000 &]
Ludic[[2000 ;; 2005]]
Select[Subsets[Select[Ludic, # < 250 &], {3}], Differences[#] == {2, 4} &]
{1, 2, 3, 5, 7, 11, 13, 17, 23, 25, 29, 37, 41, 43, 47, 53, 61, 67, 71, 77, 83, 89, 91, 97, 107}
142
{21475, 21481, 21487, 21493, 21503, 21511}
{{1, 3, 7}, {5, 7, 11}, {11, 13, 17}, {23, 25, 29}, {41, 43, 47}, {173, 175, 179}, {221, 223, 227}, {233, 235, 239}}
Perl
The "ludic" subroutine caches the longest generated sequence so far. It also generates the candidates only if no candidates remain. <lang perl>#!/usr/bin/perl use warnings; use strict; use feature qw{ say };
{ my @ludic = (1);
my $max = 3; my @candidates;
sub sieve {
my $l = shift;
for (my $i = 0; $i <= $#candidates; $i += $l) {
splice @candidates, $i, 1;
}
}
sub ludic {
my ($type, $n) = @_;
die "Arg0 Type must be 'count' or 'max'\n"
unless grep $_ eq $type, qw( count max );
die "Arg1 Number must be > 0\n" if 0 >= $n;
return (@ludic[ 0 .. $n - 1 ]) if 'count' eq $type and @ludic >= $n;
return (grep $_ <= $n, @ludic) if 'max' eq $type and $ludic[-1] >= $n;
while (1) {
if (@candidates) {
last if ('max' eq $type and $candidates[0] > $n)
or ($n == @ludic);
push @ludic, $candidates[0];
sieve($ludic[-1] - 1);
} else {
$max *= 2;
@candidates = 2 .. $max;
for my $l (@ludic) {
sieve($l - 1) unless 1 == $l;
}
}
}
return (@ludic)
}
}
my @triplet; my %ludic; undef @ludic{ ludic(max => 250) }; for my $i (keys %ludic) {
push @triplet, $i if exists $ludic{ $i + 2 } and exists $ludic { $i + 6 };
}
say 'First 25: ', join ' ', ludic(count => 25); say 'Count < 1000: ', scalar ludic(max => 1000); say '2000..2005th: ', join ' ', (ludic(count => 2005))[1999 .. 2004]; say 'triplets < 250: ', join ' ',
map { '(' . join(' ',$_, $_ + 2, $_ + 6) . ')' }
sort { $a <=> $b } @triplet;</lang>
- Output:
First 25: 1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 107 Count < 1000: 142 2000..2005th: 21475 21481 21487 21493 21503 21511 triplets < 250: (1 3 7) (5 7 11) (11 13 17) (23 25 29) (41 43 47) (173 175 179) (221 223 227) (233 235 239)
Perl 6
This implementation has no arbitrary upper limit, since it can keep adding new rotors on the fly. It just gets slower and slower instead... :-) <lang perl6>constant ludic = gather {
my @taken = take 1;
my @rotor;
for 2..* -> $i {
loop (my $j = 0; $j < @rotor; $j++) {
--@rotor[$j] or last;
}
if $j < @rotor {
@rotor[$j] = @taken[$j+1];
}
else {
push @taken, take $i;
push @rotor, @taken[$j+1];
}
}
}
say ludic[^25]; say "Number of Ludic numbers <= 1000: ", +(ludic ...^ * > 1000); say "Ludic numbers 2000..2005: ", ludic[1999..2004];
my \l250 = set ludic ...^ * > 250; say "Ludic triples < 250: ", gather
for l250.keys -> $a {
my $b = $a + 2;
my $c = $a + 6;
take "<$a $b $c>" if $b ∈ l250 and $c ∈ l250;
}</lang>
- Output:
1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 107 Number of Ludic numbers <= 1000: 142 Ludic numbers 2000..2005: 21475 21481 21487 21493 21503 21511 Ludic triples < 250: <1 3 7> <5 7 11> <11 13 17> <23 25 29> <41 43 47> <173 175 179> <221 223 227> <233 235 239>
PicoLisp
<lang PicoLisp>(de drop (Lst)
(let N (car Lst)
(make
(for (I . X) (cdr Lst)
(unless (=0 (% I N)) (link X)) ) ) ) )
(de comb (M Lst)
(cond
((=0 M) '(NIL))
((not Lst))
(T
(conc
(mapcar
'((Y) (cons (car Lst) Y))
(comb (dec M) (cdr Lst)) )
(comb M (cdr Lst)) ) ) ) )
(de ludic (N)
(let Ludic (range 1 100000)
(make
(link (pop 'Ludic))
(do (dec N)
(link (car Ludic))
(setq Ludic (drop Ludic)) ) ) ) )
(let L (ludic 2005)
(println (head 25 L))
(println (cnt '((X) (< X 1000)) L))
(println (tail 6 L))
(println
(filter
'((Lst)
(and
(= (+ 2 (car Lst)) (cadr Lst))
(= (+ 6 (car Lst)) (caddr Lst)) ) )
(comb
3
(filter '((X) (< X 250)) L) ) ) ) )
(bye)</lang>
- Output:
(1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 107) 142 (21475 21481 21487 21493 21503 21511)
((1 3 7) (5 7 11) (11 13 17) (23 25 29) (41 43 47) (173 175 179) (221 223 227) (233 235 239))
PL/I
<lang PL/I>Ludic_numbers: procedure options (main); /* 18 April 2014 */
declare V(2:22000) fixed, L(2200) fixed; declare (step, i, j, k, n) fixed binary;
Ludic: procedure;
n = hbound(V,1); k = 1; L(1) = 1; do i = 2 to n; V(i) = i; end;
do forever;
k = k + 1; L(k), step = V(2);
do i = 2 to n by step;
V(i) = 0;
end;
call compress;
if L(k) >= 21511 then leave;
end;
put skip list ('The first 25 Ludic numbers are:');
put skip edit ( (L(i) do i = 1 to 25) ) (F(4));
k = 0;
do i = 1 by 1;
if L(i) < 1000 then k = k + 1; else leave;
end;
put skip list ('There are ' || trim(k) || ' Ludic numbers < 1000');
put skip list ('Six Ludic numbers from the 2000-th:');
put skip edit ( (L(i) do i = 2000 to 2005) ) (f(7));
/* Triples are values of the form x, x+2, x+6 */
put skip list ('Triples are:');
put skip;
i = 1;
do i = 1 by 1 while (L(i+2) <= 250);
if (L(i) = L(i+1) - 2) & (L(i) = L(i+2) - 6) then
put edit ('(', L(i), L(i+1), L(i+2), ') ' ) (A, 3 F(4), A);
end;
compress: procedure;
j = 2;
do i = 2 to n;
if V(i) ^= 0 then do; V(j) = V(i); j = j + 1; end;
end;
n = j-1;
end compress;
end Ludic;
call Ludic;
end Ludic_numbers;</lang> Output:
The first 25 Ludic numbers are: 1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 107 There are 142 Ludic numbers < 1000 Six Ludic numbers from the 2000-th: 21475 21481 21487 21493 21503 21511 Triples are: ( 5 7 11) ( 11 13 17) ( 23 25 29) ( 41 43 47) ( 173 175 179) ( 221 223 227) ( 233 235 239)
Python
Python: Fast
<lang python>def ludic(nmax=100000):
yield 1
lst = list(range(2, nmax + 1))
while lst:
yield lst[0]
del lst[::lst[0]]
ludics = [l for i,l in zip(range(2005), ludic())]
print('First 25 ludic primes:') print(ludics[:25]) print("\nThere are %i ludic numbers <= 1000"
% sum(1 for l in ludics if l <= 1000))
print("\n2000'th..2005'th ludic primes:") print(ludics[2000-1: 2005])
n = 250 triplets = [(x, x+2, x+6)
for x in ludics
if x+6 < n and x+2 in ludics and x+6 in ludics]
print('\nThere are %i triplets less than %i:\n %r'
% (len(triplets), n, triplets))</lang>
- Output:
First 25 ludic primes: [1, 2, 3, 5, 7, 11, 13, 17, 23, 25, 29, 37, 41, 43, 47, 53, 61, 67, 71, 77, 83, 89, 91, 97, 107] There are 142 ludic numbers <= 1000 2000'th..2005'th ludic primes: [21475, 21481, 21487, 21493, 21503, 21511] There are 8 triplets less than 250: [(1, 3, 7), (5, 7, 11), (11, 13, 17), (23, 25, 29), (41, 43, 47), (173, 175, 179), (221, 223, 227), (233, 235, 239)]
Python: No set maximum
The following version of function ludic will return ludic numbers until reaching system limits. It is less efficient than the fast version as all lucid numbers so far are cached; on exhausting the current lst a new list of twice the size is created and the previous deletions applied before continuing. <lang python>def ludic(nmax=64):
yield 1
taken = []
while True:
lst, nmax = list(range(2, nmax + 1)), nmax * 2
for t in taken:
del lst[::t]
while lst:
t = lst[0]
taken.append(t)
yield t
del lst[::t]</lang>
Output is the same as for the fast version.
Racket
<lang racket>#lang racket (define lucid-sieve-size 25000) ; this should be enough to do me! (define lucid?
(let ((lucid-bytes-sieve
(delay
(define sieve-bytes (make-bytes lucid-sieve-size 1))
(bytes-set! sieve-bytes 0 0) ; not a lucid number
(define (sieve-pass L)
(let loop ((idx (add1 L)) (skip (sub1 L)))
(cond
[(= idx lucid-sieve-size)
(for/first ((rv (in-range (add1 L) lucid-sieve-size))
#:unless (zero? (bytes-ref sieve-bytes rv))) rv)]
[(zero? (bytes-ref sieve-bytes idx))
(loop (add1 idx) skip)]
[(= skip 0)
(bytes-set! sieve-bytes idx 0)
(loop (add1 idx) (sub1 L))]
[else (loop (add1 idx) (sub1 skip))])))
(let loop ((l 2))
(when l (loop (sieve-pass l))))
sieve-bytes)))
(λ (n) (= 1 (bytes-ref (force lucid-bytes-sieve) n)))))
(define (dnl . things) (for-each displayln things))
(dnl
"Generate and show here the first 25 ludic numbers." (for/list ((_ 25) (l (sequence-filter lucid? (in-naturals)))) l) "How many ludic numbers are there less than or equal to 1000?" (for/sum ((n 1001) #:when (lucid? n)) 1) "Show the 2000..2005'th ludic numbers." (for/list ((i 2006) (l (sequence-filter lucid? (in-naturals))) #:when (>= i 2000)) l) #<<EOS
A triplet is any three numbers x, x + 2, x + 6 where all three numbers are also ludic numbers. Show all triplets of ludic numbers < 250 (Stretch goal) EOS
(for/list ((x (in-range 250)) #:when (and (lucid? x) (lucid? (+ x 2)) (lucid? (+ x 6)))) (list x (+ x 2) (+ x 6))))</lang>
- Output:
Generate and show here the first 25 ludic numbers. (1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 107) How many ludic numbers are there less than or equal to 1000? 142 Show the 2000..2005'th ludic numbers. (21481 21487 21493 21503 21511 21523) A triplet is any three numbers x, x + 2, x + 6 where all three numbers are also ludic numbers. Show all triplets of ludic numbers < 250 (Stretch goal) ((1 3 7) (5 7 11) (11 13 17) (23 25 29) (41 43 47) (173 175 179) (221 223 227) (233 235 239)) cpu time: 18753 real time: 18766 gc time: 80
REXX
<lang rexx>/*REXX program to display (a range of) ludic numbers, or a count of same*/ parse arg N count bot top triples . /*obtain optional parameters/args*/ if N== then N=25 /*Not specified? Use the default.*/ if count== then count=1000 /* " " " " " */ if bot== then bot=2000 /* " " " " " */ if top== then top=2005 /* " " " " " */ if triples== then triples=250-1 /* " " " " " */ say 'The first ' N " ludic numbers: " ludic(n) say say "There are " words(ludic(-count)) ' ludic numbers from 1───►'count " (inclusive)." say say "The " bot ' to ' top " ludic numbers are: " ludic(bot,top) $=ludic(-triples) 0 0; #=0; @= say
do j=1 for words($); _=word($,j) /*it is known that ludic _ exists*/
if wordpos(_+2,$)==0 | wordpos(_+6,$)==0 then iterate /*¬triple.*/
#=#+1; @=@ '◄'_ _+2 _+6"► " /*bump triple counter, and ··· */
end /*j*/ /* [↑] append found triple ──► @*/
if @== then say 'From 1──►'triples", no triples found."
else say 'From 1──►'triples", " # ' triples found:' @
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────LUDIC subroutine────────────────────*/ ludic: procedure; parse arg m 1 mm,h; am=abs(m); if h\== then am=h $=1 2; @= /*$=ludic #s superset, @=# series*/
/* [↓] construct a ludic series.*/
do j=3 by 2 to am * max(1,15*((m>0)|h\==)); @=@ j; end; @=@' '
/* [↑] high limit: approx|exact */
do while words(@)\==0 /* [↓] examine the first word. */
f=word(@,1); $=$ f /*append this first word to list.*/
do d=1 by f while d<=words(@) /*use 1st #, elide all occurances*/
@=changestr(' 'word(@,d)" ",@, ' . ') /*delete the # in the seq#*/
end /*d*/ /* [↑] done eliding "1st" number*/
@=translate(@,,.) /*translate periods to blanks. */
end /*forever*/ /* [↑] done eliding ludic #s. */
@=space(@) /*remove extra blanks from list. */
if h== then return subword($,1,am) /*return a range of ludic numbers*/
return subword($,m,h-m+1) /*return a section of a range.*/</lang>
Some older REXXes don't have a changestr bif, so one is included here ──► CHANGESTR.REX.
output using the defaults for input:
The first 25 ludic numbers: 1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 107 There are 142 ludic numbers from 1───►1000 (inclusive). The 2000 to 2005 ludic numbers are: 21475 21481 21487 21493 21503 21511 From 1──►249, 8 triples found: ◄1 3 7► ◄5 7 11► ◄11 13 17► ◄23 25 29► ◄41 43 47► ◄173 175 179► ◄221 223 227► ◄233 235 239►
Ruby
<lang ruby>def ludic(nmax=100000)
Enumerator.new do |y|
y << 1
ary = *2..nmax
until ary.empty?
y << (n = ary.first)
(0...ary.size).step(n){|i| ary[i] = nil}
ary.compact!
end
end
end
puts "First 25 Ludic numbers:", ludic.first(25).to_s
puts "Ludics below 1000:", ludic(1000).count
puts "Ludic numbers 2000 to 2005:", ludic.first(2005).last(6).to_s
ludics = ludic(250).to_a puts "Ludic triples below 250:",
ludics.select{|x| ludics.include?(x+2) and ludics.include?(x+6)}.map{|x| [x, x+2, x+6]}.to_s</lang>
- Output:
First 25 Ludic numbers: [1, 2, 3, 5, 7, 11, 13, 17, 23, 25, 29, 37, 41, 43, 47, 53, 61, 67, 71, 77, 83, 89, 91, 97, 107] Ludics below 1000: 142 Ludic numbers 2000 to 2005: [21475, 21481, 21487, 21493, 21503, 21511] Ludic triples below 250: [[1, 3, 7], [5, 7, 11], [11, 13, 17], [23, 25, 29], [41, 43, 47], [173, 175, 179], [221, 223, 227], [233, 235, 239]]
Seed7
<lang seed7>$ include "seed7_05.s7i";
const func set of integer: ludicNumbers (in integer: n) is func
result
var set of integer: ludicNumbers is {1};
local
var set of integer: sieve is EMPTY_SET;
var integer: ludicNumber is 0;
var integer: number is 0;
var integer: count is 0;
begin
sieve := {2 .. n};
while sieve <> EMPTY_SET do
ludicNumber := min(sieve);
incl(ludicNumbers, ludicNumber);
count := 0;
for number range sieve do
if count rem ludicNumber = 0 then
excl(sieve, number);
end if;
incr(count);
end for;
end while;
end func;
const integer: limit is 22000; const set of integer: ludicNumbers is ludicNumbers(limit);
const proc: main is func
local
var integer: number is 0;
var integer: count is 0;
begin
write("First 25:");
for number range ludicNumbers until count = 25 do
write(" " <& number);
incr(count);
end for;
writeln;
count := 0;
for number range ludicNumbers until number > 1000 do
incr(count);
end for;
writeln("Ludics below 1000: " <& count);
write("Ludic 2000 to 2005:");
count := 0;
for number range ludicNumbers until count >= 2005 do
incr(count);
if count >= 2000 then
write(" " <& number);
end if;
end for;
writeln;
write("Triples below 250:");
for number range ludicNumbers until number > 250 do
if number + 2 in ludicNumbers and number + 6 in ludicNumbers then
write(" (" <& number <& ", " <& number + 2 <& ", " <& number + 6 <& ")");
end if;
end for;
writeln;
end func;</lang>
- Output:
First 25: 1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 107 Ludics below 1000: 142 Ludic 2000 to 2005: 21475 21481 21487 21493 21503 21511 Triples below 250: (1, 3, 7) (5, 7, 11) (11, 13, 17) (23, 25, 29) (41, 43, 47) (173, 175, 179) (221, 223, 227) (233, 235, 239)
Tcl
The limit on the number of values generated is the depth of stack; this can be set to arbitrarily deep to go as far as you want. Provided you are prepared to wait for the values to be generated. <lang tcl>package require Tcl 8.6
proc ludic n {
global ludicList ludicGenerator
for {} {[llength $ludicList] <= $n} {lappend ludicList $i} {
set i [$ludicGenerator] set ludicGenerator [coroutine L_$i apply {{gen k} { yield [info coroutine] while true { set val [$gen] if {[incr i] == $k} {set i 0} else {yield $val} } }} $ludicGenerator $i]
} return [lindex $ludicList $n]
}
- Bootstrap the generator sequence
set ludicList [list 1] set ludicGenerator [coroutine L_1 apply {{} {
set n 1
yield [info coroutine]
while true {yield [incr n]}
}}]
- Default of 1000 is not enough
interp recursionlimit {} 5000
for {set i 0;set l {}} {$i < 25} {incr i} {lappend l [ludic $i]} puts "first25: [join $l ,]"
for {set i 0} {[ludic $i] <= 1000} {incr i} {} puts "below=1000: $i"
for {set i 1999;set l {}} {$i < 2005} {incr i} {lappend l [ludic $i]} puts "2000-2005: [join $l ,]"
for {set i 0} {[ludic $i] < 256} {incr i} {set isl([ludic $i]) $i} for {set i 1;set l {}} {$i < 250} {incr i} {
if {[info exists isl($i)] && [info exists isl([expr {$i+2}])] && [info exists isl([expr {$i+6}])]} {
lappend l ($i,[expr {$i+2}],[expr {$i+6}])
}
} puts "triplets: [join $l ,]"</lang>
- Output:
first25: 1,2,3,5,7,11,13,17,23,25,29,37,41,43,47,53,61,67,71,77,83,89,91,97,107 below=1000: 142 2000-2005: 21475,21481,21487,21493,21503,21511 triplets: (1,3,7),(5,7,11),(11,13,17),(23,25,29),(41,43,47),(173,175,179),(221,223,227),(233,235,239)
zkl
This solution builds a stack of iterators, one for each Ludic number, each extending the previous iterator. A "master" iterator sits atop the stack and provides the interface to the stack. When the next Ludic number is requested, a "pulse train" ripples down and up and down ... the stack as numbers are crossed off the list(s) (figure of speech, no numbers are cached). <lang zkl>fcn dropNth(n,seq){
if(n==2) return(seq.tweak(fcn(n){ if(n.isEven) Void.Skip else n })); // uggg, special case
seq.tweak(fcn(n,skipper,w){ if(0==(w.idx+1)%skipper) Void.Skip else n }.fp1(n),
Void,Void,True); } fcn ludic{ //-->Walker
Walker(fcn(rw){ w:=rw.value; n:=w.next(); rw.set(dropNth(n,w)); n }.fp(Ref([2..]))).push(1);
}</lang> <lang zkl>ludic().walk(25).toString(*).println(); ludic().reduce(fcn(sum,n){ if(n<1000) return(sum+1); return(Void.Stop,sum); },0).println(); ludic().drop(1999).walk(6).println(); // Ludic's between 2000 & 2005
ls:=ludic().filter(fcn(n){ (n<250) and True or Void.Stop }); // Ludic's < 250 ls.filter('wrap(n){ ls.holds(n+2) and ls.holds(n+6) }).apply(fcn(n){ T(n,n+2,n+6) }).println();</lang>
- Output:
L(1,2,3,5,7,11,13,17,23,25,29,37,41,43,47,53,61,67,71,77,83,89,91,97,107) 142 L(21475,21481,21487,21493,21503,21511) L(L(1,3,7),L(5,7,11),L(11,13,17),L(23,25,29),L(41,43,47),L(173,175,179),L(221,223,227),L(233,235,239))