Self-describing numbers
You are encouraged to solve this task according to the task description, using any language you may know.
There are several so-called "self-describing" or "self-descriptive" integers.
An integer is said to be "self-describing" if it has the property that, when digit positions are labeled 0 to N-1, the digit in each position is equal to the number of times that that digit appears in the number.
For example, 2020 is a four-digit self describing number:
- position 0 has value 2 and there are two 0s in the number;
- position 1 has value 0 and there are no 1s in the number;
- position 2 has value 2 and there are two 2s;
- position 3 has value 0 and there are zero 3s.
Self-describing numbers < 100.000.000 are: 1210, 2020, 21200, 3211000, 42101000.
- Task Description
- Write a function/routine/method/... that will check whether a given positive integer is self-describing.
- As an optional stretch goal - generate and display the set of self-describing numbers.
- Related tasks
- Fours is the number of letters in the ...
- Look-and-say sequence
- Number names
- Self-referential sequence
- Spelling of ordinal numbers
11l
F is_self_describing(n)
V s = String(n)
R all(enumerate(Array(s)).map((i, ch) -> @s.count(String(i)) == Int(ch)))
print((0.<4000000).filter(x -> is_self_describing(x)))- Output:
[1210, 2020, 21200, 3211000]
360 Assembly
* Self-describing numbers 26/04/2020
SELFDESC CSECT
USING SELFDESC,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
SAVE (14,12) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
LA R8,1 k=1
DO WHILE=(C,R8,LE,=A(NN)) do k=1 to nn
CVD R8,DBLK binary to packed decimal (PL8)
MVC CK,MAK load mask
EDMK CK,DBLK+2 packed dec (PL5) to char (CL10)
S R1,=A(CK) number of blanks
LR R3,R1 "
LA R9,L'CK length(ck)
SR R9,R1 length of the number
LA R6,1 i=1
DO WHILE=(CR,R6,LE,R9) do i=1 to l
LA R10,0 n=0
LA R7,1 j=1
DO WHILE=(CR,R7,LE,R9) do j=1 to l
LA R1,CK-1 @ck
AR R1,R3 +space(k)
AR R1,R7 +j
MVC CJ,0(R1) substr(k,j,1)
IC R1,CJ ~
SLL R1,28 shift left 28
SRL R1,28 shift right 28
LR R2,R6 i
BCTR R2,0 i-1
IF CR,R1,EQ,R2 THEN if substr(k,j,1)=i-1 then
LA R10,1(R10) n++
ENDIF , endif
LA R7,1(R7) j++
ENDDO , enddo j
LA R1,CK-1 @ck
AR R1,R3 +space(k)
AR R1,R6 +i
MVC CI,0(R1) substr(k,i,1)
IC R1,CI ~
SLL R1,28 shift left 28
SRL R1,28 shift right 28
IF CR,R1,NE,R10 THEN if substr(k,i,1)<>n then
B ITERK iterate k
ENDIF , endif
LA R6,1(R6) i++
ENDDO , enddo i
XPRNT CK,L'CK print ck
ITERK LA R8,1(R8) k++
ENDDO , enddo k
L R13,4(0,R13) restore previous savearea pointer
RETURN (14,12),RC=0 restore registers from calling save
NN EQU 5000000 nn
DBLK DS PL8 double word 15num
MAK DC X'402020202020202020202020' mask CL12 11num
CK DS CL12 ck 12num
CI DS C ci
CJ DS C cj
PG DS CL80 buffer
XDEC DS CL12 temp fo xdeco
REGEQU
END SELFDESC- Output:
1210
2020
21200
3211000
Ada
with Ada.Text_IO; use Ada.Text_IO;
procedure SelfDesc is
subtype Desc_Int is Long_Integer range 0 .. 10**10-1;
function isDesc (innum : Desc_Int) return Boolean is
subtype S_Int is Natural range 0 .. 10;
type S_Int_Arr is array (0 .. 9) of S_Int;
ref, cnt : S_Int_Arr := (others => 0);
n, digit : S_Int := 0; num : Desc_Int := innum;
begin
loop
digit := S_Int (num mod 10);
ref (9 - n) := digit; cnt (digit) := cnt (digit) + 1;
num := num / 10; exit when num = 0; n := n + 1;
end loop;
return ref (9 - n .. 9) = cnt (0 .. n);
end isDesc;
begin
for i in Desc_Int range 1 .. 100_000_000 loop
if isDesc (i) then
Put_Line (Desc_Int'Image (i));
end if;
end loop;
end SelfDesc;
- Output:
1210 2020 21200 3211000 42101000
ALGOL 68
BEGIN
# return TRUE if number is self describing, FALSE otherwise #
OP SELFDESCRIBING = ( INT number )BOOL:
BEGIN
[10]INT counts := ( 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 );
INT n := number;
INT digits := 0;
# count the occurances of each digit #
WHILE
n /= 0
DO
digits +:= 1;
counts[ ( n MOD 10 ) + 1 ] +:= 1;
n OVERAB 10
OD;
# construct the number that the counts would describe, #
# if the number was self describing #
INT described number := 0;
FOR i TO digits
DO
described number *:= 10;
described number +:= counts[ i ]
OD;
# if the described number is the input number, #
# it is self describing #
( number = described number )
END; # SELFDESCRIBING #
FOR i TO 100 000 000
DO
IF SELFDESCRIBING i
THEN
print( ( i, " is self describing", newline ) )
FI
OD
END- Output:
+1210 is self describing
+2020 is self describing
+21200 is self describing
+3211000 is self describing
+42101000 is self describing
AppleScript
use AppleScript version "2.4"
use framework "Foundation"
use scripting additions
-- selfDescribes :: Int -> Bool
on selfDescribes(x)
set s to str(x)
set descripn to my str(|λ|(my groupBy(my eq, my sort(characters of s))) of my ¬
described(characters of "0123456789"))
1 = (offset of descripn in s) and ¬
0 = ((items ((length of descripn) + 1) thru -1 of s) as string as integer)
end selfDescribes
-- described :: [Char] -> [[Char]] -> [Char]
on described(digits)
script
on |λ|(groups)
if 0 < length of digits and 0 < length of groups then
set grp to item 1 of groups
set go to described(rest of digits)
if item 1 of digits = item 1 of (item 1 of grp) then
{item 1 of my str(length of grp)} & |λ|(rest of groups) of go
else
{"0"} & |λ|(groups) of go
end if
else
{}
end if
end |λ|
end script
end described
-------------------------- TEST ---------------------------
on run
script test
on |λ|(n)
str(n) & " -> " & str(selfDescribes(n))
end |λ|
end script
unlines(map(test, ¬
{1210, 1211, 2020, 2022, 21200, 21203, 3211000, 3211004}))
end run
-------------------- GENERIC FUNCTIONS --------------------
-- True if every value in the list is true.
-- and :: [Bool] -> Bool
on |and|(xs)
repeat with x in xs
if not (contents of x) then return false
end repeat
return true
end |and|
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if m ≤ n then
set lst to {}
repeat with i from m to n
set end of lst to i
end repeat
lst
else
{}
end if
end enumFromTo
-- eq (==) :: Eq a => a -> a -> Bool
on eq(a, b)
a = b
end eq
-- filter :: (a -> Bool) -> [a] -> [a]
on filter(p, xs)
tell mReturn(p)
set lst to {}
set lng to length of xs
repeat with i from 1 to lng
set v to item i of xs
if |λ|(v, i, xs) then set end of lst to v
end repeat
return lst
end tell
end filter
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- Typical usage: groupBy(on(eq, f), xs)
-- groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
on groupBy(f, xs)
set mf to mReturn(f)
script enGroup
on |λ|(a, x)
if length of (active of a) > 0 then
set h to item 1 of active of a
else
set h to missing value
end if
if h is not missing value and mf's |λ|(h, x) then
{active:(active of a) & {x}, sofar:sofar of a}
else
{active:{x}, sofar:(sofar of a) & {active of a}}
end if
end |λ|
end script
if length of xs > 0 then
set dct to foldl(enGroup, {active:{item 1 of xs}, sofar:{}}, rest of xs)
if length of (active of dct) > 0 then
sofar of dct & {active of dct}
else
sofar of dct
end if
else
{}
end if
end groupBy
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
-- The list obtained by applying f
-- to each element of xs.
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
-- 2nd class handler function lifted into 1st class script wrapper.
if script is class of f then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- sort :: Ord a => [a] -> [a]
on sort(xs)
((current application's NSArray's arrayWithArray:xs)'s ¬
sortedArrayUsingSelector:"compare:") as list
end sort
-- str :: a -> String
on str(x)
x as string
end str
-- unlines :: [String] -> String
on unlines(xs)
-- A single string formed by the intercalation
-- of a list of strings with the newline character.
set {dlm, my text item delimiters} to ¬
{my text item delimiters, linefeed}
set s to xs as text
set my text item delimiters to dlm
s
end unlines
- Output:
1210 -> true 1211 -> false 2020 -> true 2022 -> false 21200 -> true 21203 -> false 3211000 -> true 3211004 -> false
Arturo
selfDescribing?: function [x][
digs: digits x
loop.with:'i digs 'd [
if d <> size select digs 'z [z=i]
-> return false
]
return true
]
print select 1..22000 => selfDescribing?
- Output:
1210 2020 21200
AutoHotkey
Uses CountSubString: Count occurrences of a substring#AutoHotkey
; The following directives and commands speed up execution:
#NoEnv
SetBatchlines -1
ListLines Off
Process, Priority,, high
MsgBox % 2020 ": " IsSelfDescribing(2020) "`n" 1337 ": " IsSelfDescribing(1337) "`n" 1210 ": " IsSelfDescribing(1210)
Loop 100000000
If IsSelfDescribing(A_Index)
list .= A_Index "`n"
MsgBox % "Self-describing numbers < 100000000 :`n" . list
CountSubstring(fullstring, substring){
StringReplace, junk, fullstring, %substring%, , UseErrorLevel
return errorlevel
}
IsSelfDescribing(number){
Loop Parse, number
If Not CountSubString(number, A_Index-1) = A_LoopField
return false
return true
}
Output:
--------------------------- Self.ahk --------------------------- Self-describing numbers < 100000000 : 1210 2020 21200 3211000 42101000 --------------------------- OK ---------------------------
AWK
# syntax: GAWK -f SELF-DESCRIBING_NUMBERS.AWK
BEGIN {
for (n=1; n<=100000000; n++) {
if (is_self_describing(n)) {
print(n)
}
}
exit(0)
}
function is_self_describing(n, i) {
for (i=1; i<=length(n); i++) {
if (substr(n,i,1) != gsub(i-1,"&",n)) {
return(0)
}
}
return(1)
}
output:
1210 2020 21200 3211000 42101000
BASIC
Dim x, r, b, c, n, m As Integer
Dim a, d As String
Dim v(10), w(10) As Integer
Cls
For x = 1 To 5000000
a$ = ltrim$(Str$(x))
b = Len(a$)
For c = 1 To b
d$ = Mid$(a$, c, 1)
v(Val(d$)) = v(Val(d$)) + 1
w(c - 1) = Val(d$)
Next c
r = 0
For n = 0 To 10
If v(n) = w(n) Then r = r + 1
v(n) = 0
w(n) = 0
Next n
If r = 11 Then Print x; " Yes,is autodescriptive number"
Next x
Print
Print "End"
sleep
end
BBC BASIC
FOR N = 1 TO 5E7
IF FNselfdescribing(N) PRINT N
NEXT
END
DEF FNselfdescribing(N%)
LOCAL D%(), I%, L%, O%
DIM D%(9)
O% = N%
L% = LOG(N%)
WHILE N%
I% = N% MOD 10
D%(I%) += 10^(L%-I%)
N% DIV=10
ENDWHILE
= O% = SUM(D%())
Output:
1210
2020
21200
3211000
42101000
Befunge
Although we simply list the conforming numbers - nothing more.
Be aware, though, that even with a fast interpreter, it's going to be a very long time before you see the full set of results.
>1+9:0>\#06#:p#-:#1_$v
?v6:%+55:\+1\<<<\0:::<
#>g1+\6p55+/:#^_001p\v
^_@#!`<<v\+g6g10*+55\<
>:*:*:*^>>:01g1+:01p`|
^_\#\:#+.#5\#5,#$:<-$<
- Output:
1210 2020 21200 3211000 42101000
BQN
SDN ← (∧≡/)'0'-˜•Fmt
SDN¨⊸/ ↕21212
- Output:
⟨ 1210 2020 21200 ⟩
Fast generation
The full set of self-describing numbers can be found in short order from partitions of the number of digits. We'll use /⁼ to go backwards from the sorted digit list, which must have sum equal to the number of digits, to the ordered list of digits. A partition of integer k is a list of positive integers summing to k, so we get all possible sorted digit lists by padding such partitions with zeros to reach length k. This defines a self-describing number if applying /⁼ and sorting gives the same set of digits back. The code to generate partitions is taken from bqncrate.
b ← 10 # Base
m ← 20 # Maximum number of digits
S ← {(≡⟜∨¨/⊢)⟜((𝕨↑/⁼)¨) 𝕨↑¨𝕩} # Get solutions from partitions 𝕩 of 𝕨
p ← ∾¨ ∾⟜(<-⟜↕∘≠{𝕨∾¨∾(-𝕨⌊≠𝕩)↑𝕩}¨⊢)⍟m ⋈⋈⋈↕0 # Partitions of 0...m
d ← ∾ 1 ↓ (↕≠p) S¨ (∧´¨b⊸>)⊸/¨ p # Digits of self-describing numbers
b⊸×⊸+˜´∘⌽¨ d
- Output:
⟨ 2020 1210 21200 3211000 42101000 521001000 6210001000 72100001000 821000001000 9210000001000 ⟩
C
Using integers instead of strings.
#include <stdio.h>
inline int self_desc(unsigned long long xx)
{
register unsigned int d, x;
unsigned char cnt[10] = {0}, dig[10] = {0};
for (d = 0; xx > ~0U; xx /= 10)
cnt[ dig[d++] = xx % 10 ]++;
for (x = xx; x; x /= 10)
cnt[ dig[d++] = x % 10 ]++;
while(d-- && dig[x++] == cnt[d]);
return d == -1;
}
int main()
{
int i;
for (i = 1; i < 100000000; i++) /* don't handle 0 */
if (self_desc(i)) printf("%d\n", i);
return 0;
}
- Output:
1210 2020 21200 3211000 42101000
Backtracking version
Backtracks on each digit from right to left, takes advantage of constraints "sum of digit values = number of digits" and "sum of (digit index * digit value) = number of digits". It is using as argument the list of allowed digits (example 012345789 to run the program in standard base 10).
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BASE_MIN 2
#define BASE_MAX 94
void selfdesc(unsigned long);
const char *ref = "!\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~";
char *digs;
unsigned long *nums, *inds, inds_sum, inds_val, base;
int main(int argc, char *argv[]) {
int used[BASE_MAX];
unsigned long digs_n, i;
if (argc != 2) {
fprintf(stderr, "Usage is %s <digits>\n", argv[0]);
return EXIT_FAILURE;
}
digs = argv[1];
digs_n = strlen(digs);
if (digs_n < BASE_MIN || digs_n > BASE_MAX) {
fprintf(stderr, "Invalid number of digits\n");
return EXIT_FAILURE;
}
for (i = 0; i < BASE_MAX; i++) {
used[i] = 0;
}
for (i = 0; i < digs_n && strchr(ref, digs[i]) && !used[digs[i]-*ref]; i++) {
used[digs[i]-*ref] = 1;
}
if (i < digs_n) {
fprintf(stderr, "Invalid digits\n");
return EXIT_FAILURE;
}
nums = calloc(digs_n, sizeof(unsigned long));
if (!nums) {
fprintf(stderr, "Could not allocate memory for nums\n");
return EXIT_FAILURE;
}
inds = malloc(sizeof(unsigned long)*digs_n);
if (!inds) {
fprintf(stderr, "Could not allocate memory for inds\n");
free(nums);
return EXIT_FAILURE;
}
inds_sum = 0;
inds_val = 0;
for (base = BASE_MIN; base <= digs_n; base++) {
selfdesc(base);
}
free(inds);
free(nums);
return EXIT_SUCCESS;
}
void selfdesc(unsigned long i) {
unsigned long diff_sum, upper_min, j, lower, upper, k;
if (i) {
diff_sum = base-inds_sum;
upper_min = inds_sum ? diff_sum:base-1;
j = i-1;
if (j) {
lower = 0;
upper = (base-inds_val)/j;
}
else {
lower = diff_sum;
upper = diff_sum;
}
if (upper < upper_min) {
upper_min = upper;
}
for (inds[j] = lower; inds[j] <= upper_min; inds[j]++) {
nums[inds[j]]++;
inds_sum += inds[j];
inds_val += inds[j]*j;
for (k = base-1; k > j && nums[k] <= inds[k] && inds[k]-nums[k] <= i; k--);
if (k == j) {
selfdesc(i-1);
}
inds_val -= inds[j]*j;
inds_sum -= inds[j];
nums[inds[j]]--;
}
}
else {
for (j = 0; j < base; j++) {
putchar(digs[inds[j]]);
}
puts("");
}
}
- Output (for base 36):
$ time ./selfdesc.exe 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ 1210 2020 21200 3211000 42101000 521001000 6210001000 72100001000 821000001000 9210000001000 A2100000001000 B21000000001000 C210000000001000 D2100000000001000 E21000000000001000 F210000000000001000 G2100000000000001000 H21000000000000001000 I210000000000000001000 J2100000000000000001000 K21000000000000000001000 L210000000000000000001000 M2100000000000000000001000 N21000000000000000000001000 O210000000000000000000001000 P2100000000000000000000001000 Q21000000000000000000000001000 R210000000000000000000000001000 S2100000000000000000000000001000 T21000000000000000000000000001000 U210000000000000000000000000001000 V2100000000000000000000000000001000 W21000000000000000000000000000001000 real 0m0.094s user 0m0.046s sys 0m0.030s
C++
#include <iostream>
//--------------------------------------------------------------------------------------------------
typedef unsigned long long bigint;
//--------------------------------------------------------------------------------------------------
using namespace std;
//--------------------------------------------------------------------------------------------------
class sdn
{
public:
bool check( bigint n )
{
int cc = digitsCount( n );
return compare( n, cc );
}
void displayAll( bigint s )
{
for( bigint y = 1; y < s; y++ )
if( check( y ) )
cout << y << " is a Self-Describing Number." << endl;
}
private:
bool compare( bigint n, int cc )
{
bigint a;
while( cc )
{
cc--; a = n % 10;
if( dig[cc] != a ) return false;
n -= a; n /= 10;
}
return true;
}
int digitsCount( bigint n )
{
int cc = 0; bigint a;
memset( dig, 0, sizeof( dig ) );
while( n )
{
a = n % 10; dig[a]++;
cc++ ; n -= a; n /= 10;
}
return cc;
}
int dig[10];
};
//--------------------------------------------------------------------------------------------------
int main( int argc, char* argv[] )
{
sdn s;
s. displayAll( 1000000000000 );
cout << endl << endl; system( "pause" );
bigint n;
while( true )
{
system( "cls" );
cout << "Enter a positive whole number ( 0 to QUIT ): "; cin >> n;
if( !n ) return 0;
if( s.check( n ) ) cout << n << " is";
else cout << n << " is NOT";
cout << " a Self-Describing Number!" << endl << endl;
system( "pause" );
}
return 0;
}
- Output:
1210 is a Self-Describing Number. 2020 is a Self-Describing Number. 21200 is a Self-Describing Number. 3211000 is a Self-Describing Number. 42101000 is a Self-Describing Number. 521001000 is a Self-Describing Number. [...]
Alternate version
Uses C++11. Build with
g++ -std=c++11 sdn.cpp
#include <algorithm>
#include <array>
#include <iostream>
bool is_self_describing(unsigned long long int n) noexcept {
if (n == 0) {
return false;
}
std::array<char, 10> digits = {0}, counts = {0};
std::size_t i = digits.size();
do {
counts[digits[--i] = n % 10]++;
} while ((n /= 10) > 0 && i < digits.size());
return n == 0 && std::equal(begin(digits) + i, end(digits), begin(counts));
}
int main() {
for (unsigned long long int i = 0; i < 10000000000; ++i) {
if (is_self_describing(i)) {
std::cout << i << "\n";
}
}
}
Output:
1210 2020 21200 3211000 42101000 521001000 6210001000
CLU
self_describing = proc (n: int) returns (bool)
digits: array[int] := array[int]$predict(10, 10)
counts: array[int] := array[int]$fill(0, 10, 0)
while n > 0 do
digit: int := n // 10
n := n/10
array[int]$addl(digits, digit)
counts[digit] := counts[digit] + 1
end
array[int]$set_low(digits, 0)
for pos: int in array[int]$indexes(digits) do
if counts[pos] ~= digits[pos] then return(false) end
end
return(true)
end self_describing
start_up = proc ()
po: stream := stream$primary_output()
for n: int in int$from_to(1, 100000000) do
if self_describing(n) then
stream$putl(po, int$unparse(n))
end
end
end start_up- Output:
1210 2020 21200 3211000 42101000
Common Lisp
Not terribly speedy brute force. I played around with "counting" the digits directly into a number by adding in appropriate powers of 10 for each digit I see but trailing zeroes kind of gum up the works. I still think it's possible and probably much faster because it wouldn't have to allocate an array and then turn around and "interpret" it back out but I didn't really pursue it.
(defun to-ascii (str) (mapcar #'char-code (coerce str 'list)))
(defun to-digits (n)
(mapcar #'(lambda(v) (- v 48)) (to-ascii (princ-to-string n))))
(defun count-digits (n)
(do
((counts (make-array '(10) :initial-contents '(0 0 0 0 0 0 0 0 0 0)))
(curlist (to-digits n) (cdr curlist)))
((null curlist) counts)
(setf (aref counts (car curlist)) (+ 1 (aref counts (car curlist)))))))
(defun self-described-p (n)
(if (not (numberp n))
nil
(do ((counts (count-digits n))
(ipos 0 (+ 1 ipos))
(digits (to-digits n) (cdr digits)))
((null digits) t)
(if (not (eql (car digits) (aref counts ipos))) (return nil)))))
Output:
(loop for i from 1 to 4000000 do (if (self-described-p i) (print i)))
1210
2020
21200
3211000
NIL
Cowgol
include "cowgol.coh";
sub Length(n: uint32): (l: uint8) is
l := 0;
while n > 0 loop
n := n/10;
l := l+1;
end loop;
end sub;
sub IsSelfDescribing(n: uint32): (r: uint8) is
var positions: uint8[10];
var digitCounts: uint8[10];
MemSet(&positions[0], 0, @bytesof positions);
MemSet(&digitCounts[0], 0, @bytesof digitCounts);
var pos: uint8 := Length(n) - 1;
while n > 0 loop
var digit := (n % 10) as uint8;
positions[pos] := digit;
digitCounts[digit] := digitCounts[digit] + 1;
pos := pos - 1;
n := n / 10;
end loop;
r := 1;
pos := 0;
while pos < 10 loop
if positions[pos] != digitCounts[pos] then
r := 0;
break;
end if;
pos := pos + 1;
end loop;
end sub;
var n: uint32 := 1;
while n < 100000000 loop
if IsSelfDescribing(n) != 0 then
print_i32(n);
print_nl();
end if;
n := n + 1;
end loop;- Output:
1210 2020 21200 3211000 42101000
Crystal
def self_describing?(n)
digits = n.to_s.chars.map(&.to_i) # 12345 => [1, 2, 3, 4, 5]
digits.each_with_index.all? { |digit, idx| digits.count(idx) == digit }
end
t = Time.monotonic
600_000_000.times { |n| (puts "#{n} in #{(Time.monotonic - t).total_seconds} secs";\
t = Time.monotonic) if self_describing?(n) }
System: I7-6700HQ, 3.5 GHz, Linux Kernel 5.6.17, Crystal 0.35 Compil: $ crystal build selfdescribing.cr --release Run as: $ time ./selfdescribing
- Output:
1210 in 0.000403914 secs 2020 in 0.000169698 secs 21200 in 0.003607744 secs 3211000 in 0.596545807 secs 42101000 in 7.246709658 secs 521001000 in 93.020066497 secs ./selfdescribing 168.47s user 17.24s system 159% cpu 1:56.07 total
def selfDesc(n)
ns = n.to_s
nc = ns.size
count = Array.new(nc, 0)
sum = 0
while n > 0
d = n % 10
return false if d >= nc # can't have a digit >= number of digits
sum += d
return false if sum > nc
count[d] += 1
n //= 10
end
# to be self-describing sum of digits must equal number of digits
return false if sum != nc
return ns == count.join() # there must always be at least one zero
end
start = Time.monotonic
print("The self-describing numbers are:")
i = 10i64 # self-describing number must end in 0
pw = 10i64 # power of 10
fd = 1i64 # first digit
sd = 1i64 # second digit
dg = 2i64 # number of digits
mx = 11i64 # maximum for current batch
lim = 9_100_000_001i64 # sum of digits can't be more than 10
while i < lim
if selfDesc(i)
secs = (Time.monotonic - start).total_seconds
print("\n#{i} in #{secs} secs")
end
i += 10
if i > mx
fd += 1
sd -= 1
if sd >= 0
i = pw * fd
else
pw *= 10
dg += 1
i = pw
fd = 1
sd = dg - 1
end
mx = i + sd * pw // 10
end
end
osecs = (Time.monotonic - start).total_seconds
print("\nTook #{osecs} secs overall")
System: I7-6700HQ, 3.5 GHz, Linux Kernel 5.6.17, Crystal 0.35 Run as: $ crystal run selfdescribing.cr --release
- Output:
The self-describing numbers are: 1210 in 1.8045e-5 secs 2020 in 4.0684e-5 secs 21200 in 0.000105402 secs 3211000 in 0.013546922 secs 42101000 in 0.20069791 secs 521001000 in 2.775603351 secs 6210001000 in 37.813718839 secs Took 45.138222133 secs overall
D
Functional Version
import std.stdio, std.algorithm, std.range, std.conv, std.string;
bool isSelfDescribing(in long n) pure nothrow @safe {
auto nu = n.text.representation.map!q{ a - '0' };
return nu.length.iota.map!(a => nu.count(a)).equal(nu);
}
void main() {
4_000_000.iota.filter!isSelfDescribing.writeln;
}
- Output:
[1210, 2020, 21200, 3211000]
A Faster Version
bool isSelfDescribing2(ulong n) nothrow @nogc {
if (n <= 0)
return false;
__gshared static uint[10] digits, d;
digits[] = 0;
d[] = 0;
int i;
if (n < uint.max) {
uint nu = cast(uint)n;
for (i = 0; nu > 0 && i < digits.length; nu /= 10, i++) {
d[i] = nu % 10;
digits[d[i]]++;
}
if (nu > 0)
return false;
} else {
for (i = 0; n > 0 && i < digits.length; n /= 10, i++) {
d[i] = n % 10;
digits[d[i]]++;
}
if (n > 0)
return false;
}
foreach (immutable k; 0 .. i)
if (d[k] != digits[i - k - 1])
return false;
return true;
}
void main() {
import std.stdio;
foreach (immutable x; [1210, 2020, 21200, 3211000,
42101000, 521001000, 6210001000])
assert(x.isSelfDescribing2);
foreach (immutable i; 0 .. 4_000_000)
if (i.isSelfDescribing2)
i.writeln;
}
- Output:
1210 2020 21200 3211000
(About 0.29 seconds run time for 4 million tests.)
Output with foreach(i;0..600_000_000):
1210 2020 21200 3211000 42101000 521001000
Delphi
{This routine would normally be in a library. It is shown here for clarity.}
procedure GetDigitsRev(N: integer; var IA: TIntegerDynArray);
{Get an array of the integers in a number}
{Numbers returned from most to least significant}
var T,I,DC: integer;
begin
DC:=Trunc(Log10(N))+1;
SetLength(IA,DC);
for I:=DC-1 downto 0 do
begin
T:=N mod 10;
N:=N div 10;
IA[I]:=T;
end;
end;
function IsSelfDescribing(N: integer): boolean;
var IA: TIntegerDynArray;
var CA: array [0..9] of integer;
var I: integer;
begin
{Get digits, High-low order}
GetDigitsRev(N,IA);
for I:=0 to High(CA) do CA[I]:=0;
{Count number of each digit 0..9}
for I:=0 to High(IA) do
begin
CA[IA[I]]:=CA[IA[I]]+1;
end;
Result:=False;
{Compare original number with counts}
for I:=0 to High(IA) do
if IA[I]<>CA[I] then exit;
Result:=True;
end;
procedure SelfDescribingNumbers(Memo: TMemo);
var I: integer;
begin
for I:=0 to 100000000-1 do
if IsSelfDescribing(I) then
begin
Memo.Lines.Add(IntToStr(I));
end;
end;
- Output:
1210 2020 21200 3211000 42101000 Elapsed Time: 23.584 Sec.
EasyLang
Works with backtracking, iterative is too slow. Constraint: the sum of the digits count is the number of digits.
proc test d[] . .
cnt[] = [ 0 0 0 0 0 0 0 0 0 0 ]
for d in d[]
cnt[d + 1] += 1
.
for i to len d[]
if cnt[i] <> d[i]
return
.
.
# found
for d in d[]
write d
.
print ""
.
proc backtr ind max . d[] .
if ind > len d[]
test d[]
return
.
for d = 0 to max
if d < 10
d[ind] = d
backtr ind + 1 max - d d[]
.
.
.
for i = 1 to 10
len d[] i
backtr 1 len d[] d[]
.- Output:
1210 2020 21200 3211000 42101000 521001000 6210001000
Elixir
defmodule Self_describing do
def number(n) do
digits = Integer.digits(n)
Enum.map(0..length(digits)-1, fn s ->
length(Enum.filter(digits, fn c -> c==s end))
end) == digits
end
end
m = 3300000
Enum.filter(0..m, fn n -> Self_describing.number(n) end)
- Output:
[1210, 2020, 21200, 3211000]
Erlang
sdn(N) -> lists:map(fun(S)->length(lists:filter(fun(C)->C-$0==S end,N))+$0 end,lists:seq(0,length(N)-1))==N.
gen(M) -> lists:filter(fun(N)->sdn(integer_to_list(N)) end,lists:seq(0,M)).
Factor
USING: kernel math.parser prettyprint sequences ;
IN: rosetta-code.self-describing-numbers
: digits ( n -- seq ) number>string string>digits ;
: digit-count ( seq n -- m ) [ = ] curry count ;
: self-describing-number? ( n -- ? )
digits dup [ digit-count = ] with map-index [ t = ] all? ;
100,000,000 <iota> [ self-describing-number? ] filter .
- Output:
V{ 1210 2020 21200 3211000 42101000 }
Forth
\ where unavailable.
: third ( A b c -- A b c A ) >r over r> swap ;
: (.) ( u -- c-addr u ) 0 <# #s #> ;
\ COUNT is a standard word with a very different meaning, so this
\ would typically be beheaded, or given another name, or otherwise
\ given a short lifespan, so to speak.
: count ( c-addr1 u1 c -- c-addr1 u1 c+1 u )
0 2over bounds do
over i c@ = if 1+ then
loop swap 1+ swap ;
: self-descriptive? ( u -- f )
(.) [char] 0 third third bounds ?do
count i c@ [char] 0 - <> if drop 2drop false unloop exit then
loop drop 2drop true ;
FreeBASIC
' FB 1.05.0 Win64
Function selfDescribing (n As UInteger) As Boolean
If n = 0 Then Return False
Dim ns As String = Str(n)
Dim count(0 To 9) As Integer '' all elements zero by default
While n > 0
count(n Mod 10) += 1
n \= 10
Wend
For i As Integer = 0 To Len(ns) - 1
If ns[i] - 48 <> count(i) Then Return False '' numerals have ascii values from 48 to 57
Next
Return True
End Function
Print "The self-describing numbers less than 100 million are:"
For i As Integer = 0 To 99999999
If selfDescribing(i) Then Print i; " ";
Next
Print
Print "Press any key to quit"
Sleep
- Output:
The self-describing numbers less than 100 million are: 1210 2020 21200 3211000 42101000
Go
Original
package main
import (
"fmt"
"strconv"
"strings"
)
// task 1 requirement
func sdn(n int64) bool {
if n >= 1e10 {
return false
}
s := strconv.FormatInt(n, 10)
for d, p := range s {
if int(p)-'0' != strings.Count(s, strconv.Itoa(d)) {
return false
}
}
return true
}
// task 2 code (takes a while to run)
func main() {
for n := int64(0); n < 1e10; n++ {
if sdn(n) {
fmt.Println(n)
}
}
}
Output produced by above program:
1210 2020 21200 3211000 42101000 521001000 6210001000
Optimized
Uses the optimized loop from the Wren entry - 12 times faster than before.
package main
import (
"fmt"
"strconv"
"strings"
"time"
)
func selfDesc(n uint64) bool {
if n >= 1e10 {
return false
}
s := strconv.FormatUint(n, 10)
for d, p := range s {
if int(p)-'0' != strings.Count(s, strconv.Itoa(d)) {
return false
}
}
return true
}
func main() {
start := time.Now()
fmt.Println("The self-describing numbers are:")
i := uint64(10) // self-describing number must end in 0
pw := uint64(10) // power of 10
fd := uint64(1) // first digit
sd := uint64(1) // second digit
dg := uint64(2) // number of digits
mx := uint64(11) // maximum for current batch
lim := uint64(9_100_000_001) // sum of digits can't be more than 10
for i < lim {
if selfDesc(i) {
secs := time.Since(start).Seconds()
fmt.Printf("%d (in %.1f secs)\n", i, secs)
}
i += 10
if i > mx {
fd++
sd--
if sd >= 0 {
i = fd * pw
} else {
pw *= 10
dg++
i = pw
fd = 1
sd = dg - 1
}
mx = i + sd*pw/10
}
}
osecs := time.Since(start).Seconds()
fmt.Printf("\nTook %.1f secs overall\n", osecs)
}
- Output:
Timings are for an Intel Core i7-8565U machine running Go 1.14.2 on Ubuntu 18.04.
The self-describing numbers are: 1210 (in 0.0 secs) 2020 (in 0.0 secs) 21200 (in 0.0 secs) 3211000 (in 0.0 secs) 42101000 (in 0.2 secs) 521001000 (in 2.5 secs) 6210001000 (in 29.9 secs) Took 43.0 secs overall
Haskell
import Data.Char
count :: Int -> [Int] -> Int
count x = length . filter (x ==)
isSelfDescribing :: Integer -> Bool
isSelfDescribing n = nu == f
where
nu = digitToInt <$> show n
f = (`count` nu) <$> [0 .. length nu - 1]
main :: IO ()
main = do
print $
isSelfDescribing <$>
[1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000]
print $ filter isSelfDescribing [0 .. 4000000]
Output:
[True,True,True,True,True,True,True] [1210,2020,21200,3211000]
Here are functions for generating all the self-describing numbers of a certain length. We capitalize on the fact (from Wikipedia) that a self-describing number of length n is a base-n number (i.e. all digits are 0..n-1).
import Control.Monad (forM_, replicateM)
import Data.Char (intToDigit)
count :: Int -> [Int] -> Int
count x = length . filter (x ==)
-- All the combinations of n digits of base n.
-- A base-n number is represented as a list of ints,
-- one per digit
allBaseNNumsOfLength :: Int -> [[Int]]
allBaseNNumsOfLength =
replicateM
<*> (enumFromTo 0 . subtract 1)
isSelfDescribing :: [Int] -> Bool
isSelfDescribing num =
all (\(i, x) -> x == count i num) $
zip [0 ..] num
-- Translated back into an integer in base-10
decimalize :: [Int] -> Int
decimalize = read . map intToDigit
main :: IO ()
main =
(print . concat) $
map decimalize
. filter isSelfDescribing
. allBaseNNumsOfLength
<$> [1 .. 8]
- Output:
[1210,2020,21200,3211000,42101000]
Icon and Unicon
The following program contains the procedure is_self_describing to test if a number is a self-describing number, and the procedure self_describing_numbers to generate them.
A slightly more concise solution can be derived from the above by taking more advantage of Icon's (and Unicon's) automatic goal-directed evaluation:
procedure is_self_describing (n)
ns := string (n) # convert to a string
every i := 1 to *ns do {
if count (string(i-1), ns) ~= ns[i] then fail
}
return n # on success, return the self-described number
end
procedure self_describing_numbers ()
suspend is_self_describing(seq())
end
J
Solution:
digits =: 10&#.^:_1
counts =: _1 + [: #/.~ i.@:# , ]
selfdesc =: = counts&.digits"0 NB. Note use of "under"
Example:
selfdesc 2020 1210 21200 3211000 43101000 42101000
1 1 1 1 0 1
Extra credit:
I.@:selfdesc i. 1e6
1210 2020 21200
Discussion: The use of &. here is a great example of its surprisingly broad applicability, and the elegance it can produce.
The use of "0 is less satisfying, expressing an essentially scalar solution, and that such an approach runs against the grain of J becomes quite evident when executing the extra credit sentence.
It would not be difficult to rephrase the verb in a way that would take advantage of J's array mastery, but it would cost us of some of the simplicity and elegance of the existing solution. More gratifying would be some kind of closed-form, algebraic formula that could identify the SDNs directly, without test-and-filter.
That said, note that this is an incomplete implementation of the extra-credit problem -- and, hypothetically speaking, numbers longer than 9 digits could be valid results in the extra-credit problem (we just have to be sure that digit positions which are not occupied by digits we can represent have 0 for their count). This might allow us to treat numbers up to just under 19 digits as self describing numbers. This is a slightly larger range of numbers than we get for positive integers from signed 64 bit representation. So a proper solution to this problem on currently available hardware (one that finds the complete result in some useful span of time) probably should use a non-brute-force solution.
Java
public class SelfDescribingNumbers{
public static boolean isSelfDescribing(int a){
String s = Integer.toString(a);
for(int i = 0; i < s.length(); i++){
String s0 = s.charAt(i) + "";
int b = Integer.parseInt(s0); // number of times i-th digit must occur for it to be a self describing number
int count = 0;
for(int j = 0; j < s.length(); j++){
int temp = Integer.parseInt(s.charAt(j) + "");
if(temp == i){
count++;
}
if (count > b) return false;
}
if(count != b) return false;
}
return true;
}
public static void main(String[] args){
for(int i = 0; i < 100000000; i++){
if(isSelfDescribing(i)){
System.out.println(i);
}
}
}
}
JavaScript
function is_self_describing(n) {
var digits = Number(n).toString().split("").map(function(elem) {return Number(elem)});
var len = digits.length;
var count = digits.map(function(x){return 0});
digits.forEach(function(digit, idx, ary) {
if (digit >= count.length)
return false
count[digit] ++;
});
return digits.equals(count);
}
Array.prototype.equals = function(other) {
if (this === other)
return true; // same object
if (this.length != other.length)
return false;
for (idx in this)
if (this[idx] !== other[idx])
return false;
return true;
}
for (var i=1; i<=3300000; i++)
if (is_self_describing(i))
print(i);
outputs
1210 2020 21200 3211000
jq
# If your jq includes all/2 then comment out the following definition,
# which is slightly less efficient:
def all(generator; condition):
reduce generator as $i (true; if . then $i | condition else . end);def selfie:
def count(value): reduce .[] as $i (0; if $i == value then . + 1 else . end);
def digits: tostring | explode | map(. - 48);
digits
| if add != length then false
else . as $digits
| all ( range(0; length); . as $i | $digits | (.[$i] == count($i)) )
end;The task:
range(0; 100000001) | select(selfie)- Output:
$ jq -n -f Self-describing_numbers.jq
1210
2020
21200
3211000
42101000
Julia
function selfie(x::Integer)
ds = reverse(digits(x))
if sum(ds) != length(ds) return false end
for (i, d) in enumerate(ds)
if d != sum(ds .== i - 1) return false end
end
return true
end
@show selfie(2020)
@show selfie(2021)
selfies(x) = for i in 1:x selfie(i) && println(i) end
@time selfies(4000000)
- Output:
1210 2020 21200 3211000 1.398922 seconds (8.01 M allocations: 1.049 GiB, 6.91% gc time)
K
sdn: {n~+/'n=/:!#n:0$'$x}'
sdn 1210 2020 2121 21200 3211000 42101000
1 1 0 1 1 1
&sdn@!:1e6
1210 2020 21200
Kotlin
// version 1.0.6
fun selfDescribing(n: Int): Boolean {
if (n <= 0) return false
val ns = n.toString()
val count = IntArray(10)
var nn = n
while (nn > 0) {
count[nn % 10] += 1
nn /= 10
}
for (i in 0 until ns.length)
if( ns[i] - '0' != count[i]) return false
return true
}
fun main(args: Array<String>) {
println("The self-describing numbers less than 100 million are:")
for (i in 0..99999999) if (selfDescribing(i)) print("$i ")
println()
}
- Output:
The self-describing numbers less than 100 million are: 1210 2020 21200 3211000 42101000
Liberty BASIC
'adapted from BASIC solution
FOR x = 1 TO 5000000
a$ = TRIM$(STR$(x))
b = LEN(a$)
FOR c = 1 TO b
d$ = MID$(a$, c, 1)
v(VAL(d$)) = v(VAL(d$)) + 1
w(c - 1) = VAL(d$)
NEXT c
r = 0
FOR n = 0 TO 10
IF v(n) = w(n) THEN r = r + 1
v(n) = 0
w(n) = 0
NEXT n
IF r = 11 THEN PRINT x; " is a self-describing number"
NEXT x
PRINT
PRINT "End"LiveCode
function selfDescNumber n
local tSelfD, tLen
put len(n) into tLen
repeat with x = 0 to (tLen - 1)
put n into nCopy
replace x with empty in nCopy
put char (x + 1) of n = (tLen - len(nCopy)) into tSelfD
if not tSelfD then exit repeat
end repeat
return tSelfD
end selfDescNumberTo list the self-describing numbers to 10 million
on mouseUp
repeat with n = 0 to 10000000
if selfDescNumber(n) then
put n into selfNum[n]
end if
end repeat
combine selfNum using comma
put selfNum
end mouseUpOutput
1210,2020,21200,3211000Logo
TO XX
BT
MAKE "AA (ARRAY 10 0)
MAKE "BB (ARRAY 10 0)
FOR [Z 0 9][SETITEM :Z :AA "0 SETITEM :Z :BB "0 ]
FOR [A 1 50000][
MAKE "B COUNT :A
MAKE "Y 0
MAKE "X 0
MAKE "R 0
MAKE "J 0
MAKE "K 0
FOR [C 1 :B][MAKE "D ITEM :C :A
SETITEM :C - 1 :AA :D
MAKE "X ITEM :D :BB
MAKE "Y :X + 1
SETITEM :D :BB :Y
MAKE "R 0]
FOR [Z 0 9][MAKE "J ITEM :Z :AA
MAKE "K ITEM :Z :BB
IF :J = :K [MAKE "R :R + 1]]
IF :R = 10 [PR :A]
FOR [Z 0 9][SETITEM :Z :AA "0 SETITEM :Z :BB "0 ]]
PR [END]
ENDLua
function Is_self_describing( n )
local s = tostring( n )
local t = {}
for i = 0, 9 do t[i] = 0 end
for i = 1, s:len() do
local idx = tonumber( s:sub(i,i) )
t[idx] = t[idx] + 1
end
for i = 1, s:len() do
if t[i-1] ~= tonumber( s:sub(i,i) ) then return false end
end
return true
end
for i = 1, 999999999 do
print( Is_self_describing( i ) )
end
Mathematica /Wolfram Language
isSelfDescribing[n_Integer] := (RotateRight[DigitCount[n]] == PadRight[IntegerDigits[n], 10])
Select[Range[10^10 - 1], isSelfDescribing]
-> {1210,2020,21200,3211000,42101000,521001000,6210001000}
MATLAB / Octave
function z = isSelfDescribing(n)
s = int2str(n)-'0'; % convert to vector of digits
y = hist(s,0:9);
z = all(y(1:length(s))==s);
end;
Test function:
for k = 1:1e10,
if isSelfDescribing(k),
printf('%i\n',k);
end
end;
Output:
1210 2020 21200 ...
MiniScript
numbers = [12, 1210, 1300, 2020, 21200, 5]
occurrences = function(test, values)
count = 0
for i in values
if i.val == test then count = count + 1
end for
return count
end function
for number in numbers
check = "" + number
digits = check.values
describing = true
for digit in digits.indexes
if digits[digit].val != occurrences(digit, digits) then
describing = false
end if
end for
if describing then
print number + " is self describing"
else
print number + " is not self describing"
end if
end for
- Output:
12 is not self describing 1210 is self describing 1300 is not self describing 2020 is self describing 21200 is self describing 5 is not self describing
Modula-2
MODULE SelfDescribingNumber;
FROM WholeStr IMPORT
CardToStr;
FROM STextIO IMPORT
WriteString, WriteLn;
FROM SWholeIO IMPORT
WriteCard;
PROCEDURE Check(Number: CARDINAL): BOOLEAN;
VAR
I, D: CARDINAL;
A: ARRAY [0 .. 9] OF CHAR;
Count, W: ARRAY [0 .. 9] OF CARDINAL;
Result: BOOLEAN;
BEGIN
CardToStr(Number, A);
FOR I := 0 TO 9 DO
Count[I] := 0;
W[I] := 0;
END;
FOR I := 0 TO LENGTH(A) - 1 DO
D := ORD(A[I]) - ORD("0");
INC(Count[D]);
W[I] := D;
END;
Result := TRUE;
I := 0;
WHILE Result AND (I <= 9) DO
Result := (Count[I] = W[I]);
INC(I);
END;
RETURN Result;
END Check;
VAR
X: CARDINAL;
BEGIN
WriteString("Autodescriptive numbers from 1 to 100000000:");
WriteLn;
FOR X := 1 TO 100000000 DO
IF Check(X) THEN
WriteString(" ");
WriteCard(X, 1);
WriteLn;
END;
END;
WriteString("Job done.");
WriteLn;
END SelfDescribingNumber.
- Output:
Autodescriptive numbers from 1 to 100000000: 1210 2020 21200 3211000 42101000 Job done.
Nim
This is a brute-force algorithm. To speed-up, it uses integers instead of strings and the variable “digits” is allocated once, placed in global scope and accessed directly by the two functions (something I generally avoid). We have been able to check until 1_000_000_000.
import algorithm, sequtils, std/monotimes, times
type Digit = 0..9
var digits = newSeqOfCap[Digit](10)
proc getDigits(n: Positive) =
digits.setLen(0)
var n = n.int
while n != 0:
digits.add n mod 10
n = n div 10
digits.reverse()
proc isSelfDescribing(n: Natural): bool =
n.getDigits()
for i, d in digits:
if digits.count(i) != d:
return false
result = true
let t0 = getMonoTime()
for n in 1 .. 1_000_000_000:
if n.isSelfDescribing:
echo n, " in ", getMonoTime() - t0
echo "\nTotal time: ", getMonoTime() - t0
- Output:
1210 in 154 microseconds and 723 nanoseconds 2020 in 376 microseconds and 687 nanoseconds 21200 in 2 milliseconds, 804 microseconds, and 259 nanoseconds 3211000 in 165 milliseconds, 490 microseconds, and 749 nanoseconds 42101000 in 2 seconds, 89 milliseconds, 515 microseconds, and 202 nanoseconds 521001000 in 27 seconds, 712 milliseconds, 35 microseconds, and 660 nanoseconds Total time: 52 seconds, 969 milliseconds, 578 microseconds, and 698 nanoseconds
ooRexx
-- REXX program to check if a number (base 10) is self-describing.
parse arg x y .
if x=='' then exit
if y=='' then y=x
-- 10 digits is the maximum size number that works here, so cap it
numeric digits 10
y=min(y, 9999999999)
loop number = x to y
loop i = 1 to number~length
digit = number~subchar(i)
-- return on first failure
if digit \= number~countstr(i - 1) then iterate number
end
say number "is a self describing number"
end
output when using the input of: 0 999999999
1210 is a self-describing number. 2020 is a self-describing number. 21200 is a self-describing number. 3211000 is a self-describing number. 42101000 is a self-describing number. 521001000 is a self-describing number. 6210001000 is a self-describing number.
PARI/GP
This is a finite set...
S=[1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000];
isself(n)=vecsearch(S,n)Pascal
Program SelfDescribingNumber;
uses
SysUtils;
function check(number: longint): boolean;
var
i, d: integer;
a: string;
count, w : array [0..9] of integer;
begin
a := intToStr(number);
for i := 0 to 9 do
begin
count[i] := 0;
w[i] := 0;
end;
for i := 1 to length(a) do
begin
d := ord(a[i]) - ord('0');
inc(count[d]);
w[i - 1] := d;
end;
check := true;
i := 0;
while check and (i <= 9) do
begin
check := count[i] = w[i];
inc(i);
end;
end;
var
x: longint;
begin
writeln ('Autodescriptive numbers from 1 to 100000000:');
for x := 1 to 100000000 do
if check(x) then
writeln (' ', x);
writeln('Job done.');
end.
Output:
:> ./SelfDescribingNumber Autodescriptive numbers from 1 to 100000000: 1210 2020 21200 3211000 42101000 Job done.
Perl
The idea is to make two arrays: the first one contains the digits at their positions and the second one contains the digits counts.
The number is self-descriptive If the arrays are equal.
sub is_selfdesc
{
local $_ = shift;
my @b = (0) x length;
$b[$_]++ for my @a = split //;
return "@a" eq "@b";
}
# check all numbers from 0 to 100k plus two 'big' ones
for (0 .. 100000, 3211000, 42101000) {
print "$_\n" if is_selfdesc($_);
}
Output:
1210 2020 21200 3211000 42101000
Phix
with javascript_semantics function self_desc(integer i) sequence digits = repeat(0,10), counts = repeat(0,10) integer n = 0, digit while 1 do digit := mod(i,10) digits[10-n] := digit digit += 1 counts[digit] += 1 i = floor(i/10) if i=0 then exit end if n += 1 end while return digits[10-n..10] = counts[1..n+1] end function atom t0 = time() for i=10 to 100_000_000 by 10 do if self_desc(i) then ?i end if end for printf(1,"done (%s)\n",{elapsed(time()-t0)})
- Output:
1210 2020 21200 3211000 42101000 done (21.78s)
generator
Not quite as fast as I hoped it would be, although a bazillion times faster than the above and a good five times faster than Python, the following self(20) completes in just over a second whereas self(24) takes nearly 9s, and it continues getting exponentially slower after that. Curiously, it is the early stages (same output) that slow down, whereas the latter ones always complete fairly quickly.
with javascript_semantics procedure impl(sequence d, c, integer m) if m>=0 then integer l = length(d) if l and d == c[1..l] then string ds = "" for i=1 to l do integer ch = d[i]+'0' if ch>'9' then ch += 'a'-'9'-1 end if ds &= ch end for printf(1,"%s\n",ds) end if sequence dd = deep_copy(d)&0 for i=c[l+1] to m do dd[$] = i integer i1 = i+1 if i>l or c[i1]!=dd[i1] then c[i1] += 1 impl(dd,deep_copy(c),m-i) c[i1] -= 1 end if end for end if end procedure procedure self(integer n) atom t0 = time() impl({}, repeat(0,n+1), n) ?elapsed(time()-t0) end procedure self(20)
- Output:
1210 2020 21200 3211000 42101000 521001000 6210001000 72100001000 821000001000 9210000001000 a2100000001000 b21000000001000 c210000000001000 d2100000000001000 e21000000000001000 f210000000000001000 g2100000000000001000 "1.2s"
even faster
Finishes in less than a tenth of a second
with javascript_semantics constant string aleph = tagset('9','0')&tagset('z','a')&tagset('Z','A') -- ie "0123456789abc..zABC..Z" (62 characters) procedure gen(integer n) for ones=iff(n>=7?2:0) to min(2,n-3) do sequence digits = repeat(0,n), counts = repeat(0,n) digits[1] := n-2-ones if digits[1]<>2 then digits[digits[1]+1] := 1 digits[2] := 2 digits[3] := 1 else digits[2] := (ones<>0) digits[3] := 2 end if for i=1 to n do integer d11 = digits[i]+1 counts[d11] += 1 end for if counts=digits then string s = "" for i=1 to n do integer di = digits[i] s &= aleph[di+1] end for printf(1,"%s\n",s) end if end for end procedure atom t0 = time() for n=1 to length(aleph)+3 do gen(n) end for ?elapsed(time()-t0)
- Output:
as above plus
h21000000000000001000 i210000000000000001000 ... z21000000000000000000000000000000001000 A210000000000000000000000000000000001000 ... Z2100000000000000000000000000000000000000000000000000000000001000 "0.0s"
PHP
Works with: PHP 5.
<?php
function is_describing($number) {
foreach (str_split((int) $number) as $place => $value) {
if (substr_count($number, $place) != $value) {
return false;
}
}
return true;
}
for ($i = 0; $i <= 50000000; $i += 10) {
if (is_describing($i)) {
echo $i . PHP_EOL;
}
}
?>
Output:
1210 2020 21200 3211000 42101000
Picat
Here are three approaches. The latter two use a constraint modelling approach (a variant to the classic magic sequence problem, see below).
Loop based approach
self_desc(Num,L) =>
L = [ I.to_integer() : I in Num.to_string()],
Len = L.len,
if sum(L) != Len then fail end,
foreach(J in L)
% cannot be a digit larger than the length of Num
if J >= Len then fail end
end,
foreach(I in 0..Len-1)
if sum([1 : J in L, I==J]) != L[I+1] then
fail
end
end.Constraint model 1
Check if a number N is a self-describing number
self_desc_cp(Num, Sequence) =>
N = length(Num.to_string()),
Sequence = new_list(N),
Sequence :: 0..N-1,
foreach(I in 0..N-1) count(I,Sequence,#=,Sequence[I+1]) end,
N #= sum(Sequence),
to_num(Sequence,10,Num),
scalar_product({ I : I in 0..N-1}, Sequence, N),
solve([ffd,updown], Sequence).Constraint model 2
Same idea as self_desc_cp/2 but a different usage: generate all solutions of a specific length Len.
self_desc_cp_len(Len, Num) =>
Sequence = new_list(Len),
Sequence :: 0..Len-1,
Len #= sum(Sequence),
scalar_product({ I : I in 0..Len-1}, Sequence, Len),
to_num(Sequence,10,Num),
foreach(I in 0..Len-1) count(I,Sequence,#=,Sequence[I+1]) end,
solve([ffc,inout], Sequence).
%
% Converts a number Num to/from a list of integer List given a base Base
%
to_num(List, Base, Num) =>
Len = length(List),
Num #= sum([List[I]*Base**(Len-I) : I in 1..Len]).Testing
Testing some numbers using self_desc_cp/2:
go =>
List = [1210, 2020, 21200, 3211000, 42101000,
123456,98,10,-121,0,1,
9210000001000],
foreach(N in List)
printf("%w: %w\n", N, cond(self_desc_cp(N,_S),"self desc", "not self desc"))
end,
nl.- Output:
2020: self desc 21200: self desc 3211000: self desc 42101000: self desc 123456: not self desc 98: not self desc 10: not self desc -121: not self desc 0: not self desc 1: not self desc 9210000001000: self desc
Generate all solutions of a specific length
Using self_desc_cp_len/3 to generates all solutions of length 1..13:
go2 =>
Len :: 1..13,
println(findall(Num, (indomain(Len), self_desc_cp_len(Len,Num)))),
nl.- Output:
[1210,2020,21200,3211000,42101000,521001000,6210001000,72100001000,821000001000,9210000001000]
Magic sequence
The two constraint modelling approaches are variations of the classic magic sequence problem:
A magic sequence of length n is a sequence of integers x0 . . xn-1 between 0 and n-1, such that for all i in 0 to n-1, the number i occurs exactly xi times in the sequence. For instance, 6,2,1,0,0,0,1,0,0,0 is a magic sequence since 0 occurs 6 times in it, 1 occurs twice.
Here is one way to model this magic sequence problem.
go3 ?=>
member(N, 4..1000),
magic_sequenceN,Seq),
println(N=Seq),
fail,
nl.
go3 => true.
magic_sequence(N, Sequence) =>
Sequence = new_list(N),
Sequence :: 0..N-1,
foreach(I in 0..N-1)
Sequence[I+1] #= sum([Sequence[J] #= I : J in 1..N])
end,
sum(Sequence) #= N,
sum([I*Sequence[I+1] : I in 0..N-1]) #= N,
solve([ff,split], Sequence).- Output:
4 = [1,2,1,0] 4 = [2,0,2,0] 5 = [2,1,2,0,0] 7 = [3,2,1,1,0,0,0] 8 = [4,2,1,0,1,0,0,0] 9 = [5,2,1,0,0,1,0,0,0] 10 = [6,2,1,0,0,0,1,0,0,0] 11 = [7,2,1,0,0,0,0,1,0,0,0] 12 = [8,2,1,0,0,0,0,0,1,0,0,0] 13 = [9,2,1,0,0,0,0,0,0,1,0,0,0] 14 = [10,2,1,0,0,0,0,0,0,0,1,0,0,0] 15 = [11,2,1,0,0,0,0,0,0,0,0,1,0,0,0] 16 = [12,2,1,0,0,0,0,0,0,0,0,0,1,0,0,0] 17 = [13,2,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 18 = [14,2,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 19 = [15,2,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 20 = [16,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 21 = [17,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 22 = [18,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 23 = [19,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 24 = [20,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 25 = [21,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 26 = [22,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 27 = [23,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 28 = [24,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 29 = [25,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 30 = [26,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 31 = [27,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 32 = [28,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 33 = [29,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 34 = [30,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 35 = [31,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 36 = [32,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 37 = [33,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 38 = [34,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 39 = [35,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] 40 = [36,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0] ...
Algorithmic approach
Except for the self describing number 2020, these sequences can be found by the following "algorithmic" approach:
magic_sequence_alg(N, Sequence) =>
Sequence = new_list(N,0),
Sequence[1] := N - 4,
Sequence[2] := 2,
Sequence[3] := 1,
Sequence[N-3] := 1.PicoLisp
(de selfDescribing (N)
(fully '((D I) (= D (cnt = N (circ I))))
(setq N (mapcar format (chop N)))
(range 0 (length N)) ) )Output:
: (filter selfDescribing (range 1 4000000)) -> (1210 2020 21200 3211000)
PowerShell
According to the Wiki definition, the sum of the products of the index and the digit contained at the index should equal the number of digits in the number:
function Test-SelfDescribing ([int]$Number)
{
[int[]]$digits = $Number.ToString().ToCharArray() | ForEach-Object {[Char]::GetNumericValue($_)}
[int]$sum = 0
for ($i = 0; $i -lt $digits.Count; $i++)
{
$sum += $i * $digits[$i]
}
$sum -eq $digits.Count
}
Test-SelfDescribing -Number 2020
- Output:
True
It takes a very long while to test 100,000,000 numbers, and since they are already known just test a few:
11,2020,21200,321100 | ForEach-Object {
[PSCustomObject]@{
Number = $_
IsSelfDescribing = Test-SelfDescribing -Number $_
}
} | Format-Table -AutoSize
- Output:
Number IsSelfDescribing
------ ----------------
11 False
2020 True
21200 True
321100 False
Prolog
Works with SWI-Prolog and library clpfd written by Markus Triska.
:- use_module(library(clpfd)).
self_describling :-
forall(between(1, 10, I),
(findall(N, self_describling(I,N), L),
format('Len ~w, Numbers ~w~n', [I, L]))).
% search of the self_describling numbers of a given len
self_describling(Len, N) :-
length(L, Len),
Len1 is Len - 1,
L = [H|T],
% the first figure is greater than 0
H in 1..Len1,
% there is a least to figures so the number of these figures
% is at most Len - 2
Len2 is Len - 2,
T ins 0..Len2,
% the sum of the figures is equal to the len of the number
sum(L, #=, Len),
% There is at least one figure corresponding to the number of zeros
H1 #= H+1,
element(H1, L, V),
V #> 0,
% create the list
label(L),
% test the list
msort(L, LNS),
packList(LNS,LNP),
numlist(0, Len1, NumList),
verif(LNP,NumList, L),
% list is OK, create the number
maplist(atom_number, LA, L),
number_chars(N, LA).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% testing a number (not use in this program)
self_describling(N) :-
number_chars(N, L),
maplist(atom_number, L, LN),
msort(LN, LNS),
packList(LNS,LNP), !,
length(L, Len),
Len1 is Len - 1,
numlist(0, Len1, NumList),
verif(LNP,NumList, LN).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% verif(PackList, Order_of_Numeral, Numeral_of_the_nuber_to_test)
% Packlist is of the form [[Number_of_Numeral, Order_of_Numeral]|_]
% Test succeed when
% All lists are empty
verif([], [], []).
% Packlist is empty and all lasting numerals are 0
verif([], [_N|S], [0|T]) :-
verif([], S, T).
% Number of numerals N is V
verif([[V, N]|R], [N|S], [V|T]) :-
verif(R, S, T).
% Number of numerals N is 0
verif([[V, N1]|R], [N|S], [0|T]) :-
N #< N1,
verif([[V,N1]|R], S, T).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% ?- packList([a,a,a,b,c,c,c,d,d,e], L).
% L = [[3,a],[1,b],[3,c],[2,d],[1,e]] .
% ?- packList(R, [[3,a],[1,b],[3,c],[2,d],[1,e]]).
% R = [a,a,a,b,c,c,c,d,d,e] .
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
packList([],[]).
packList([X],[[1,X]]) :- !.
packList([X|Rest],[XRun|Packed]):-
run(X,Rest, XRun,RRest),
packList(RRest,Packed).
run(Var,[],[1, Var],[]).
run(Var,[Var|LRest],[N1, Var],RRest):-
N #> 0,
N1 #= N + 1,
run(Var,LRest,[N, Var],RRest).
run(Var,[Other|RRest], [1, Var],[Other|RRest]):-
dif(Var,Other).
Output
?- self_describling. Len 1, Numbers [] Len 2, Numbers [] Len 3, Numbers [] Len 4, Numbers [1210,2020] Len 5, Numbers [21200] Len 6, Numbers [] Len 7, Numbers [3211000] Len 8, Numbers [42101000] Len 9, Numbers [521001000] Len 10, Numbers [6210001000] true.
PureBasic
Procedure isSelfDescribing(x.q)
;returns 1 if number is self-describing, otherwise it returns 0
Protected digitCount, digit, i, digitSum
Dim digitTally(10)
Dim digitprediction(10)
If x <= 0
ProcedureReturn 0 ;number must be positive and non-zero
EndIf
While x > 0 And i < 10
digit = x % 10
digitSum + digit
If digitSum > 10
ProcedureReturn 0 ;sum of digits' values exceeds maximum possible
EndIf
digitprediction(i) = digit
digitTally(digit) + 1
x / 10
i + 1
Wend
digitCount = i - 1
If digitSum < digitCount Or x > 0
ProcedureReturn 0 ;sum of digits' values is too small or number has more than 10 digits
EndIf
For i = 0 To digitCount
If digitTally(i) <> digitprediction(digitCount - i)
ProcedureReturn 0 ;number is not self-describing
EndIf
Next
ProcedureReturn 1 ;number is self-describing
EndProcedure
Procedure displayAll()
Protected i, j, t
PrintN("Starting search for all self-describing numbers..." + #CRLF$)
For j = 0 To 9
PrintN(#CRLF$ + "Searching possibilites " + Str(j * 1000000000) + " -> " + Str((j + 1) * 1000000000 - 1)+ "...")
t = ElapsedMilliseconds()
For i = 0 To 999999999
If isSelfDescribing(j * 1000000000 + i)
PrintN(Str(j * 1000000000 + i))
EndIf
Next
PrintN("Time to search this range of possibilities: " + Str((ElapsedMilliseconds() - t) / 1000) + "s.")
Next
PrintN(#CRLF$ + "Search complete.")
EndProcedure
If OpenConsole()
DataSection
Data.q 1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000, 3214314
EndDataSection
Define i, x.q
For i = 1 To 8
Read.q x
Print(Str(x) + " is ")
If Not isSelfDescribing(x)
Print("not ")
EndIf
PrintN("selfdescribing.")
Next
PrintN(#CRLF$)
displayAll()
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf
Sample output:
1210 is selfdescribing. 2020 is selfdescribing. 21200 is selfdescribing. 3211000 is selfdescribing. 42101000 is selfdescribing. 521001000 is selfdescribing. 6210001000 is selfdescribing. 3214314 is not selfdescribing. Starting search for all self-describing numbers... Searching possibilites 0 -> 999999999... 1210 2020 21200 3211000 42101000 521001000 Time to search this range of possibilities: 615s. Searching possibilites 1000000000 -> 1999999999... Time to search this range of possibilities: 614s. Searching possibilites 2000000000 -> 2999999999... Time to search this range of possibilities: 628s. Searching possibilites 3000000000 -> 3999999999... Time to search this range of possibilities: 631s. Searching possibilites 4000000000 -> 4999999999... Time to search this range of possibilities: 630s. Searching possibilites 5000000000 -> 5999999999... Time to search this range of possibilities: 628s. Searching possibilites 6000000000 -> 6999999999... 6210001000 Time to search this range of possibilities: 629s. Searching possibilites 7000000000 -> 7999999999... Time to search this range of possibilities: 631s. Searching possibilites 8000000000 -> 8999999999... Time to search this range of possibilities: 629s. Searching possibilites 9000000000 -> 9999999999... Time to search this range of possibilities: 629s. Search complete.
Python
>>> def isSelfDescribing(n):
s = str(n)
return all(s.count(str(i)) == int(ch) for i, ch in enumerate(s))
>>> [x for x in range(4000000) if isSelfDescribing(x)]
[1210, 2020, 21200, 3211000]
>>> [(x, isSelfDescribing(x)) for x in (1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000)]
[(1210, True), (2020, True), (21200, True), (3211000, True), (42101000, True), (521001000, True), (6210001000, True)]
Generator
From here.
def impl(d, c, m):
if m < 0: return
if d == c[:len(d)]: print d
for i in range(c[len(d)],m+1):
dd = d+[i]
if i<len(dd) and c[i]==dd[i]: continue
impl(dd,c[:i]+[c[i]+1]+c[i+1:],m-i)
def self(n): impl([], [0]*(n+1), n)
self(10)
Output:
[] [1, 2, 1, 0] [2, 0, 2, 0] [2, 1, 2, 0, 0] [3, 2, 1, 1, 0, 0, 0] [4, 2, 1, 0, 1, 0, 0, 0] [5, 2, 1, 0, 0, 1, 0, 0, 0] [6, 2, 1, 0, 0, 0, 1, 0, 0, 0]
Quackery
[ tuck over peek
1+ unrot poke ] is item++ ( n [ --> [ )
[ [] 10 times [ 0 join ]
swap
[ 10 /mod rot item++
swap dup 0 = until ]
drop ] is digitcount ( n --> [ )
[ 0 swap witheach + ] is sum ( [ --> n )
[ 0 swap
witheach
[ swap 10 * + ] ] is digits->n ( [ --> n )
[ dup digitcount
dup sum split drop
digits->n = ] is self-desc ( n --> b )
4000000 times
[ i^ self-desc if
[ i^ echo cr ] ]- Output:
1210 2020 21200 3211000
Racket
#lang racket
(define (get-digits number (lst null))
(if (zero? number)
lst
(get-digits (quotient number 10) (cons (remainder number 10) lst))))
(define (self-describing? number)
(if (= number 0) #f
(let ((digits (get-digits number)))
(for/fold ((bool #t))
((i (in-range (length digits))))
(and bool
(= (count (lambda (x) (= x i)) digits)
(list-ref digits i)))))))
Sadly, the implementation is too slow for the optional task, taking somewhere around 3 minutes to check all numbers below 100.000.000
Raku
(formerly Perl 6)
my @values = <1210 2020 21200 3211000
42101000 521001000 6210001000 27 115508>;
for @values -> $test {
say "$test is {sdn($test) ?? '' !! 'NOT ' }a self describing number.";
}
sub sdn($n) {
my $s = $n.Str;
my $chars = $s.chars;
my @a = +«$s.comb;
my @b;
for @a -> $i {
return False if $i >= $chars;
++@b[$i];
}
@b[$_] //= 0 for ^$chars;
@a eqv @b;
}
.say if .&sdn for ^9999999;
Output:
1210 is a self describing number. 2020 is a self describing number. 21200 is a self describing number. 3211000 is a self describing number. 42101000 is a self describing number. 521001000 is a self describing number. 6210001000 is a self describing number. 27 is NOT a self describing number. 115508 is NOT a self describing number. 1210 2020 21200 3211000
Red
Red []
;;-------------------------------------
count-dig: func ["count occurence of digit in number"
;;-------------------------------------
s [string!] "number as string"
sdig [char!] "search number as char"
][
cnt: #"0" ;; counter as char for performance optimization
while [s: find/tail s sdig][cnt: cnt + 1]
return cnt
]
;;-------------------------------------
isSDN?: func ["test if number is self describing number"
s [string!] "number to test as string "
][
;;-------------------------------------
ind: #"0" ;; use digit as char for performance optimization
foreach ele s [
if ele <> count-dig s ind [return false]
ind: ind + 1
]
return true
]
repeat i 4000000 [ if isSDN? to-string i [print i] ]
output
1210 2020 21200 3211000 >>
REXX
Also see: OEIS A46043 and OEIS A138480.
digit by digit test
/*REXX program determines if a number (in base 10) is a self─describing, */
/*────────────────────────────────────────────────────── self─descriptive, */
/*────────────────────────────────────────────────────── autobiographical, or a */
/*────────────────────────────────────────────────────── curious number. */
parse arg x y . /*obtain optional arguments from the CL*/
if x=='' | x=="," then exit /*Not specified? Then get out of Dodge*/
if y=='' | y=="," then y=x /* " " Then use the X value.*/
w=length(y) /*use Y's width for aligned output. */
numeric digits max(9, w) /*ensure we can handle larger numbers. */
if x==y then do /*handle the case of a single number. */
noYes=test_SDN(y) /*is it or ain't it? */
say y word("is isn't", noYes+1) 'a self-describing number.'
exit
end
do n=x to y
if test_SDN(n) then iterate /*if not self─describing, try again. */
say right(n,w) 'is a self-describing number.' /*is it? */
end /*n*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
test_SDN: procedure; parse arg ?; L=length(?) /*obtain the argument and its length.*/
do j=L to 1 by -1 /*parsing backwards is slightly faster.*/
if substr(?,j,1)\==L-length(space(translate(?,,j-1),0)) then return 1
end /*j*/
return 0 /*faster if used inverted truth table. */
╔══════════════════════════════════════════════════════════════════╗
║ The method used above is to TRANSLATE the digit being queried to ║
║ blanks, then use the SPACE BIF function to remove all blanks, ║
║ and then compare the new number's length to the original length. ║
║ ║
║ The difference in length is the number of digits translated. ║
╚══════════════════════════════════════════════════════════════════╝
output when using the input of: 0 9999999999
1210 is a self-describing number.
2020 is a self-describing number.
21200 is a self-describing number.
3211000 is a self-describing number.
42101000 is a self-describing number.
521001000 is a self-describing number.
6210001000 is a self-describing number.
faster method
(Uses table lookup.)
/*REXX program determines if a number (in base 10) is a self-describing number.*/
parse arg x y . /*obtain optional arguments from the CL*/
if x=='' | x=="," then exit /*Not specified? Then get out of Dodge*/
if y=='' | y=="," then y=x /*Not specified? Then use the X value.*/
w=length(y) /*use Y's width for aligned output. */
numeric digits max(9, w) /*handle the possibility of larger #'s.*/
$= '1210 2020 21200 3211000 42101000 521001000 6210001000' /*the list of numbers.*/
/*test for a single integer. */
if x==y then do /*handle the case of a single number. */
say word("isn't is", wordpos(x, $) + 1) 'a self-describing number.'
exit
end
/* [↓] test for a range of integers.*/
do n=x to y; parse var n '' -1 _ /*obtain the last decimal digit of N. */
if _\==0 then iterate
if wordpos(n, $)==0 then iterate
say right(n,w) 'is a self-describing number.'
end /*n*/
/*stick a fork in it, we're all done. */
output is the same as the 1st REXX example.
fastest method
(Uses a table look-up.)
(Results are instantaneous.)
/*REXX program determines if a number (in base 10) is a self-describing number.*/
parse arg x y . /*obtain optional arguments from the CL*/
if x=='' | x=="," then exit /*Not specified? Then get out of Dodge*/
if y=='' | y=="," then y=x /*Not specified? Then use the X value.*/
w=length(y) /*use Y's width for aligned output. */
numeric digits max(9, w) /*handle the possibility of larger #'s.*/
$= '1210 2020 21200 3211000 42101000 521001000 6210001000' /*the list of numbers.*/
/*test for a single integer. */
if x==y then do /*handle the case of a single number. */
say word("isn't is", wordpos(x, $) + 1) 'a self-describing number.'
exit
end
/* [↓] test for a range of integers.*/
do n=1 for words($); _=word($, n) /*look for integers that are in range. */
if _<x | _>y then iterate /*if not self-describing, try again. */
say right(_, w) 'is a self-describing number.'
end /*n*/ /*stick a fork in it, we're all done. */
output is the same as the 1st REXX example.
Ring
# Project : Self-describing numbers
for num = 1 to 45000000
res = 0
for n=1 to len(string(num))
temp = string(num)
pos = number(temp[n])
cnt = count(temp,string(n-1))
if cnt = pos
res = res + 1
ok
next
if res = len(string(num))
see num + nl
ok
next
func count(cString,dString)
sum = 0
while substr(cString,dString) > 0
sum = sum + 1
cString = substr(cString,substr(cString,dString)+len(string(sum)))
end
return sumOutput:
1210 2020 21200 3211000 42101000
RPL
With some reasoning, one can find that digits must be between 0 and 4: just try manually to make a SDN with a 5 or greater and you will see it's impossible. The task enumerator takes this into account by counting in base 5, skipping numbers whose digital root is not equal to the number of digits and adding a final zero. Brute force is 30 times slower.
≪ STR→ { }
1 PICK3 SIZE FOR j
OVER j DUP SUB STR→ + NEXT
1 SF
0 ROT SIZE 1 - FOR j
DUP j 1 + GET
IF OVER 1 ≪ j == ≫ DOLIST ∑LIST ≠ THEN
1 CF DUP SIZE 'j' STO END
NEXT NIP
1 FS?
≫ 'SELF?' STO
≪ →STR
1 OVER SIZE 1 - SUB @ remove final zero
0
1 PICK 3 SIZE FOR j
5 * OVER j DUP SUB STR→ + NEXT @ convert from base 5
NIP DUP
DO
DROP 1 + DUP ""
DO SWAP 5 IDIV2 ROT + @ convert to base 5
UNTIL OVER NOT END
NIP STR→
UNTIL DUP 1 - 9 MOD OVER XPON 1 + == END @ check digital root
NIP 10 * @ add final zero
≫ 'NEXTCAND' STO
≪ → max
≪ { } 10
WHILE DUP max < REPEAT
IF DUP SELF? THEN SWAP OVER + SWAP END
NEXTCAND
END DROP
≫ ≫ 'TASK' STO
9999 TASK
- Output:
1: {1210 2020}
Runs in 43 seconds on a HP-48G.
Ruby
def self_describing?(n)
digits = n.digits.reverse
digits.each_with_index.all?{|digit, idx| digits.count(idx) == digit}
end
3_300_000.times {|n| puts n if self_describing?(n)}
outputs
1210 2020 21200 3211000
def selfDesc(n)
ns = n.to_s
nc = ns.size
count = Array.new(nc, 0)
sum = 0
while n > 0
d = n % 10
return false if d >= nc # can't have a digit >= number of digits
sum += d
return false if sum > nc
count[d] += 1
n /= 10
end
# to be self-describing sum of digits must equal number of digits
return false if sum != nc
return ns == count.join() # there must always be at least one zero
end
start = Time.now
print("The self-describing numbers are:")
i = 10 # self-describing number must end in 0
pw = 10 # power of 10
fd = 1 # first digit
sd = 1 # second digit
dg = 2 # number of digits
mx = 11 # maximum for current batch
lim = 9_100_000_001 # sum of digits can't be more than 10
while i < lim
if selfDesc(i)
secs = (Time.now - start) #.total_seconds
print("\n#{i} in #{secs} secs")
end
i += 10
if i > mx
fd += 1
sd -= 1
if sd >= 0
i = pw * fd
else
pw *= 10
dg += 1
i = pw
fd = 1
sd = dg - 1
end
mx = i + sd * pw / 10
end
end
osecs = (Time.now - start)
print("\nTook #{osecs} secs overall")
System: I7-6700HQ, 3.5 GHz, Linux Kernel 5.6.17, Ruby 2.7.1 Run as: $ ruby selfdescribing.rb
- Output:
The self-describing numbers are: 1210 in 5.5602e-05 secs 2020 in 8.2552e-05 secs 21200 in 0.000755124 secs 3211000 in 0.096793633 secs 42101000 in 1.417997487 secs 521001000 in 19.847824233 secs 6210001000 in 278.414668197 secs Took 332.50934836 secs overall
System: I7-6700HQ, 3.5 GHz, Linux Kernel 5.6.17, JRuby 9.2.11.1 Run as: $ ruby selfdescribing.rb
- Output:
The self-describing numbers are: 1210 in 0.01568 secs 2020 in 0.024242 secs 21200 in 0.037699 secs 3211000 in 0.297682 secs 42101000 in 1.156694 secs 521001000 in 13.114478 secs 6210001000 in 181.24703 secs Took 216.292875 secs overall
System: I7-6700HQ, 3.5 GHz, Linux Kernel 5.6.17, TruffleRuby 20.1.0 Run as: $ ruby selfdescribing.rb
- Output:
The self-describing numbers are: 1210 in 0.005 secs 2020 in 0.006 secs 21200 in 0.0130 secs 3211000 in 0.252 secs 42101000 in 0.642 secs 521001000 in 2.231 secs 6210001000 in 97.064 secs Took 123.061 secs overall
Run BASIC
for i = 0 to 50000000 step 10
a$ = str$(i)
for c = 1 TO len(a$)
d = val(mid$(a$, c, 1))
j(d) = j(d) + 1
k(c-1) = d
next c
r = 0
for n = 0 to 10
r = r + (j(n) = k(n))
j(n) = 0
k(n) = 0
next n
if r = 11 then print i
next i
print "== End =="
endRust
fn is_self_desc(xx: u64) -> bool
{
let s: String = xx.to_string();
let mut count_vec = vec![0; 10];
for c in s.chars() {
count_vec[c.to_digit(10).unwrap() as usize] += 1;
}
for (i, c) in s.chars().enumerate() {
if count_vec[i] != c.to_digit(10).unwrap() as usize {
return false;
}
}
return true;
}
fn main() {
for i in 1..100000000 {
if is_self_desc(i) {
println!("{}", i)
}
}
}
Scala
Functional Programming
object SelfDescribingNumbers extends App {
def isSelfDescribing(a: Int): Boolean = {
val s = Integer.toString(a)
(0 until s.length).forall(i => s.count(_.toString.toInt == i) == s(i).toString.toInt)
}
println("Curious numbers n = x0 x1 x2...x9 such that xi is the number of digits equal to i in n.")
for (i <- 0 to 42101000 by 10
if isSelfDescribing(i)) println(i)
println("Successfully completed without errors.")
}
See it running in your browser by Scastie (JVM).
Seed7
$ include "seed7_05.s7i";
const func boolean: selfDescr (in string: stri) is func
result
var boolean: check is TRUE;
local
var integer: idx is 0;
var array integer: count is [0 .. 9] times 0;
begin
for idx range 1 to length(stri) do
incr(count[ord(stri[idx]) - ord('0')]);
end for;
idx := 1;
while check and idx <= length(stri) do
check := count[pred(idx)] = ord(stri[idx]) - ord('0');
incr(idx);
end while;
end func;
const proc: gen (in integer: n) is func
local
var array integer : digits is 0 times 0;
var string: stri is "";
var integer: numberOfOneDigits is 0;
var integer: idx is 0;
begin
while numberOfOneDigits <= 2 and numberOfOneDigits < n - 2 do
digits := n times 0;
digits[1] := n - 2 - numberOfOneDigits;
if digits[1] <> 2 then
digits[digits[1] + 1] := 1;
digits[2] := 2;
digits[3] := 1;
else
digits[2] := ord(numberOfOneDigits <> 0);
digits[3] := 2;
end if;
stri := "";
for idx range 1 to n do
stri &:= chr(ord(digits[idx]) + ord('0'));
end for;
if selfDescr(stri) then
writeln(stri);
end if;
incr(numberOfOneDigits);
end while;
end func;
const proc: main is func
local
const array integer: nums is [] (1210, 1337, 2020, 21200, 3211000, 42101000);
var integer: number is 0;
begin
for number range nums do
write(number <& " is ");
if not selfDescr(str(number)) then
write("not ");
end if;
writeln("self describing");
end for;
writeln;
writeln("All autobiograph numbers:");
for number range 1 to 10 do
gen(number);
end for;
end func;Output:
1210 is self describing 1337 is not self describing 2020 is self describing 21200 is self describing 3211000 is self describing 42101000 is self describing All autobiograph numbers: 2020 1210 21200 3211000 42101000 521001000 6210001000
Sidef
func sdn(Number n) {
var b = [0]*n.len
var a = n.digits.flip
a.each { |i| b[i] := 0 ++ }
a == b
}
var values = [1210, 2020, 21200, 3211000,
42101000, 521001000, 6210001000, 27, 115508]
values.each { |test|
say "#{test} is #{sdn(test) ? '' : 'NOT ' }a self describing number."
}
say "\nSelf-descriptive numbers less than 1e5 (in base 10):"
^1e5 -> each { |i| say i if sdn(i) }
- Output:
1210 is a self describing number. 2020 is a self describing number. 21200 is a self describing number. 3211000 is a self describing number. 42101000 is a self describing number. 521001000 is a self describing number. 6210001000 is a self describing number. 27 is NOT a self describing number. 115508 is NOT a self describing number. Self-descriptive numbers less than 1e5 (in base 10): 1210 2020 21200
Extra credit: this will generate all the self-describing numbers in bases 7 to 36:
for b in (7 .. 36) {
var n = ((b-4) * b**(b-1) + 2*(b**(b-2)) + b**(b-3) + b**3 -> base(b))
say "base #{'%2d' % b}: #{n}"
}
- Output:
base 7: 3211000 base 8: 42101000 base 9: 521001000 base 10: 6210001000 base 11: 72100001000 base 12: 821000001000 base 13: 9210000001000 base 14: a2100000001000 base 15: b21000000001000 base 16: c210000000001000 base 17: d2100000000001000 base 18: e21000000000001000 base 19: f210000000000001000 base 20: g2100000000000001000 base 21: h21000000000000001000 base 22: i210000000000000001000 base 23: j2100000000000000001000 base 24: k21000000000000000001000 base 25: l210000000000000000001000 base 26: m2100000000000000000001000 base 27: n21000000000000000000001000 base 28: o210000000000000000000001000 base 29: p2100000000000000000000001000 base 30: q21000000000000000000000001000 base 31: r210000000000000000000000001000 base 32: s2100000000000000000000000001000 base 33: t21000000000000000000000000001000 base 34: u210000000000000000000000000001000 base 35: v2100000000000000000000000000001000 base 36: w21000000000000000000000000000001000
Swift
import Foundation
extension BinaryInteger {
@inlinable
public var isSelfDescribing: Bool {
let stringChars = String(self).map({ String($0) })
let counts = stringChars.reduce(into: [Int: Int](), {res, char in res[Int(char), default: 0] += 1})
for (i, n) in stringChars.enumerated() where counts[i, default: 0] != Int(n) {
return false
}
return true
}
}
print("Self-describing numbers less than 100,000,000:")
DispatchQueue.concurrentPerform(iterations: 100_000_000) {i in
defer {
if i == 100_000_000 - 1 {
exit(0)
}
}
guard i.isSelfDescribing else {
return
}
print(i)
}
dispatchMain()
- Output:
Self-describing numbers less than 100,000,000: 1210 2020 21200 3211000 42101000
Tcl
package require Tcl 8.5
proc isSelfDescribing num {
set digits [split $num ""]
set len [llength $digits]
set count [lrepeat $len 0]
foreach d $digits {
if {$d >= $len} {return false}
lset count $d [expr {[lindex $count $d] + 1}]
}
foreach d $digits c $count {if {$c != $d} {return false}}
return true
}
for {set i 0} {$i < 100000000} {incr i} {
if {[isSelfDescribing $i]} {puts $i}
}
Uiua
Not massively fast, so let's not go too far. Takes about 15s even so.
# Split, dupe, check size of number before generating it.
IsSdn ← ⨬(/↧=≡(/+=)⊙¤°⊏|0)>10/+..≡⋕°⋕
▽⊸≡IsSdn ⇡5e6- Output:
[1210 2020 21200 3211000]
UNIX Shell
Seeking self-describing numbers up to 100,000,000 is very time consuming, so we'll just verify a few numbers.
selfdescribing() {
local n=$1
local count=()
local i
for ((i=0; i<${#n}; i++)); do
((count[${n:i:1}]++))
done
for ((i=0; i<${#n}; i++)); do
(( ${n:i:1} == ${count[i]:-0} )) || return 1
done
return 0
}
for n in 0 1 10 11 1210 2020 21200 3211000 42101000; do
if selfdescribing $n; then
printf "%d\t%s\n" $n yes
else
printf "%d\t%s\n" $n no
fi
done
- Output:
0 no 1 no 10 no 11 no 1210 yes 2020 yes 21200 yes 3211000 yes 42101000 yes
VBScript
Takes a very, very long time to check 100M numbers that I have to terminate the script. But the function works.
Function IsSelfDescribing(n)
IsSelfDescribing = False
Set digit = CreateObject("Scripting.Dictionary")
For i = 1 To Len(n)
k = Mid(n,i,1)
If digit.Exists(k) Then
digit.Item(k) = digit.Item(k) + 1
Else
digit.Add k,1
End If
Next
c = 0
For j = 0 To Len(n)-1
l = Mid(n,j+1,1)
If digit.Exists(CStr(j)) Then
If digit.Item(CStr(j)) = CInt(l) Then
c = c + 1
End If
ElseIf l = 0 Then
c = c + 1
Else
Exit For
End If
Next
If c = Len(n) Then
IsSelfDescribing = True
End If
End Function
'testing
start_time = Now
s = ""
For m = 1 To 100000000
If IsSelfDescribing(m) Then
WScript.StdOut.WriteLine m
End If
Next
end_time = Now
WScript.StdOut.WriteLine "Elapse Time: " & DateDiff("s",start_time,end_time) & " seconds"
Wren
Heavily optimized to complete the search in a reasonable time for a scripting language.
var selfDesc = Fn.new { |n|
var ns = "%(n)"
var nc = ns.count
var count = List.filled(nc, 0)
var sum = 0
while (n > 0) {
var d = n % 10
if (d >= nc) return false // can't have a digit >= number of digits
sum = sum + d
if (sum > nc) return false
count[d] = count[d] + 1
n = (n/10).floor
}
// to be self-describing sum of digits must equal number of digits
if (sum != nc) return false
return ns == count.join() // there must always be at least one zero
}
var start = System.clock
System.print("The self-describing numbers are:")
var i = 10 // self-describing number must end in 0
var pw = 10 // power of 10
var fd = 1 // first digit
var sd = 1 // second digit
var dg = 2 // number of digits
var mx = 11 // maximum for current batch
var lim = 9.1 * 1e9 + 1 // sum of digits can't be more than 10
while (i < lim) {
if (selfDesc.call(i)) {
var secs = ((System.clock - start) * 10).round / 10
System.print("%(i) (in %(secs) secs)")
}
i = i + 10
if (i > mx) {
fd = fd + 1
sd = sd - 1
if (sd >= 0) {
i = fd * pw
} else {
pw = pw * 10
dg = dg + 1
i = pw
fd = 1
sd = dg - 1
}
mx = i + sd*pw/10
}
}
var osecs = ((System.clock - start) * 10).round / 10
System.print("\nTook %(osecs) secs overall")
- Output:
Timings are for an Intel Core i7-8565U machine running Wren 0.2.0 on Ubuntu 18.04.
The self-describing numbers are: 1210 (in 0 secs) 2020 (in 0 secs) 21200 (in 0 secs) 3211000 (in 0.3 secs) 42101000 (in 4.8 secs) 521001000 (in 72.9 secs) 6210001000 (in 1162.5 secs) Took 1392.1 secs overall
XPL0
code ChOut=8, IntOut=11;
func SelfDesc(N); \Returns 'true' if N is self-describing
int N;
int Len, \length = number of digits in N
I, D;
char Digit(10), Count(10);
proc Num2Str(N); \Convert integer N to string in Digit
int N;
int R;
[N:= N/10;
R:= rem(0);
if N then Num2Str(N);
Digit(Len):= R;
Len:= Len+1;
];
[Len:= 0;
Num2Str(N);
for I:= 0 to Len-1 do Count(I):= 0;
for I:= 0 to Len-1 do
[D:= Digit(I);
if D >= Len then return false;
Count(D):= Count(D)+1;
];
for I:= 0 to Len-1 do
if Count(I) # Digit(I) then return false;
return true;
]; \SelfDesc
int N;
for N:= 0 to 100_000_000-1 do
if SelfDesc(N) then [IntOut(0, N); ChOut(0, ^ )]Output:
1210 2020 21200 3211000 42101000
Yabasic
FOR N = 1 TO 5E7
IF FNselfdescribing(N) PRINT N
NEXT
sub FNselfdescribing(N)
LOCAL D(9), I, L, O
O = N
L = INT(LOG(N, 10))
WHILE(N)
I = MOD(N, 10)
D(I) = D(I) + 10^(L-I)
N = INT(N / 10)
WEND
L = 0
FOR I = 0 TO 8 : L = L + D(I) : NEXT
RETURN O = L
END SUBZig
const std = @import("std");
// Return true if number is self describing
fn isSelfDescribing(number: u32) bool {
var n = number; // Zig parameters are immutable, copy to var.
// 10 is the maximum number of decimal digits in a 32-bit integer.
var array: [10]u32 = undefined;
// Add digits to array.
var i: u32 = 0;
while (n != 0 or i == 0) : (n /= 10) {
array[i] = n % 10;
i += 1;
}
var digits = array[0..i]; // Slice to give just the digits added.
std.mem.reverse(u32, digits);
// Check digits. Brute force.
for (digits, 0..) |predicted_count, predicted_digit| {
var count: u8 = 0;
for (digits) |digit| {
if (digit == predicted_digit) count += 1;
}
if (count != predicted_count) return false;
}
return true;
}
pub fn main() anyerror!void {
const stdout = std.io.getStdOut().writer();
for (0..100_000_000) |number| {
if (isSelfDescribing(@intCast(number)))
try stdout.print("{}\n", .{number});
}
}
- Output:
1210 2020 21200 3211000 42101000
Alternative With "Optimizations"
Here is an alternative implementation of isSelfDescribing() that illustrates additional computationally cheap ways of partially eliminating integers that are not self describing. These ideas were filched from other solutions on this page (primarily Wren & PowerShell). The code works. Refactoring for speed is a further exercise.
/// Return true if number is self describing
fn isSelfDescribing(number: u32) bool {
// Get the digits (limit scope of variables in a Zig block expression)
// 1234 -> { 1, 2, 3, 4}
const digits = blk: {
var n = number; // Zig parameters are immutable, copy to var.
// 10 is the maximum number of decimal digits in a 32-bit integer.
var array: [10]u32 = undefined;
// Add base 10 digits to array.
var i: u32 = 0;
while (n != 0 or i == 0) : (n /= 10) {
array[i] = n % 10;
i += 1;
}
var slice = array[0..i]; // Slice to give only the digits added.
std.mem.reverse(u32, slice);
break :blk slice;
};
{
// wikipedia: last digit must be zero
if (digits[digits.len - 1] != 0) return false;
}
{
// cannot have a digit >= number of digits
for (digits) |n| if (n >= digits.len) return false;
}
{
// sum of digits must equal number of digits
var sum: u32 = 0;
for (digits) |n| sum += n; // > digits.len short-circuit ?
if (sum != digits.len) return false;
}
{
// sum of the products of the index and the digit contained at the index
// should equal the number of digits in the number
var sum: u32 = 0;
for (digits, 0..) |n, index| sum += n * @as(u32, @truncate(index));
if (sum != digits.len) return false;
}
// Final elimination. 100% effective. Brute force.
{
// Self describing check of digits.
for (digits, 0..) |expected_count, expected_digit| {
var count: u8 = 0;
for (digits) |digit| {
if (digit == expected_digit) count += 1;
}
if (count != expected_count) return false;
}
}
return true;
}
zkl
fcn isSelfDescribing(n){
if (n.bitAnd(1)) return(False); // Wikipedia: last digit must be zero
nu:= n.toString();
ns:=["0".."9"].pump(String,nu.inCommon,"len"); //"12233".inCommon("2")-->"22"
(nu+"0000000000")[0,10] == ns; //"2020","2020000000"
}Since testing a humongous number of numbers is slow, chunk the task into a bunch of threads. Even so, it pegged my 8 way Ivy Bridge Linux box for quite some time (eg the Python & AWK solutions crush this one).
//[1..0x4_000_000].filter(isSelfDescribing).println();
const N=0d500_000;
[1..0d100_000_000, N] // chunk and thread, 200 in this case
.apply(fcn(n){ n.filter(N,isSelfDescribing) }.future)
.filter().apply("noop").println();A future is a thread returning a [delayed] result, future.filter/future.noop will block until the future coughs up the result. Since the results are really sparse for the bigger numbers, filter out the empty results.
- Output:
L(L(1210,2020,21200),L(3211000),L(42101000))
Categories:
- Clarified and Needing Review
- Programming Tasks
- Solutions by Programming Task
- 11l
- 360 Assembly
- Ada
- ALGOL 68
- AppleScript
- Arturo
- AutoHotkey
- AWK
- BASIC
- BBC BASIC
- Befunge
- BQN
- C
- C++
- CLU
- Common Lisp
- Cowgol
- Crystal
- D
- Delphi
- SysUtils,StdCtrls
- EasyLang
- Elixir
- Erlang
- Factor
- Forth
- FreeBASIC
- Go
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Jq
- Julia
- K
- Kotlin
- Liberty BASIC
- LiveCode
- Logo
- Lua
- Mathematica
- Wolfram Language
- MATLAB
- Octave
- MiniScript
- Modula-2
- Nim
- OoRexx
- PARI/GP
- Pascal
- Perl
- Phix
- PHP
- Picat
- PicoLisp
- PowerShell
- Prolog
- PureBasic
- Python
- Quackery
- Racket
- Raku
- Red
- REXX
- Ring
- RPL
- Ruby
- Run BASIC
- Rust
- Scala
- Seed7
- Sidef
- Swift
- Tcl
- Uiua
- UNIX Shell
- VBScript
- Wren
- XPL0
- Yabasic
- Zig
- Zkl