Super-d numbers: Difference between revisions
(julia example) |
(Added FreeBASIC) |
||
(55 intermediate revisions by 27 users not shown) | |||
Line 1: | Line 1: | ||
{{task}} |
{{task}} |
||
A super-d number is a positive, decimal (base ten) integer '''n''' such that '''d × n |
A super-d number is a positive, decimal (base ten) integer '''n''' such that '''d × n<sup>d</sup>''' has at least '''d''' consecutive digits '''d''' where |
||
where |
|||
<big>2 ≤ d ≤ 9</big> |
<big>2 ≤ d ≤ 9</big> |
||
For instance, 753 is a super-3 number because 3 × 753 |
For instance, 753 is a super-3 number because 3 × 753<sup>3</sup> = 128087<u>333</u>1. |
||
Line 10: | Line 9: | ||
;Task |
;Task: |
||
:* Write a function/procedure/routine to find super-d numbers. |
:* Write a function/procedure/routine to find super-d numbers. |
||
:* For '''d=2''' through '''d=6''', use the routine to show the first '''10''' super-d numbers. |
:* For '''d=2''' through '''d=6''', use the routine to show the first '''10''' super-d numbers. |
||
;Extra credit |
;Extra credit: |
||
:* Show the first '''10''' super-7, super-8, and/or super-9 numbers (optional). |
|||
:* Show the first '''10''' super-7, super-8, and/or super-9 numbers. (Optional) |
|||
;See also: |
|||
:* [http://mathworld.wolfram.com/Super-dNumber.html Wolfram MathWorld - Super-d Number]. |
|||
:* [http://oeis.org/A014569 OEIS: A014569 - Super-3 Numbers]. |
|||
<br><br> |
|||
=={{header|11l}}== |
|||
;See also |
|||
{{trans|D}} |
|||
<syntaxhighlight lang="11l">V rd = [‘22’, ‘333’, ‘4444’, ‘55555’, ‘666666’, ‘7777777’, ‘88888888’, ‘999999999’] |
|||
:* '''[http://mathworld.wolfram.com/Super-dNumber.html Wolfram MathWorld - Super-d Number]''' |
|||
:* '''[http://oeis.org/A014569 OEIS: A014569 - Super-3 Numbers]''' |
|||
L(ii) 2..7 |
|||
print(‘First 10 super-#. numbers:’.format(ii)) |
|||
V count = 0 |
|||
BigInt j = 3 |
|||
L |
|||
V k = ii * j^ii |
|||
I rd[ii - 2] C String(k) |
|||
count++ |
|||
print(j, end' ‘ ’) |
|||
I count == 10 |
|||
print("\n") |
|||
L.break |
|||
j++</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 10 super-2 numbers: |
|||
19 31 69 81 105 106 107 119 127 131 |
|||
First 10 super-3 numbers: |
|||
261 462 471 481 558 753 1036 1046 1471 1645 |
|||
First 10 super-4 numbers: |
|||
1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
First 10 super-5 numbers: |
|||
4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
First 10 super-6 numbers: |
|||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
First 10 super-7 numbers: |
|||
140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 |
|||
</pre> |
|||
=={{header|Amazing Hopper}}== |
|||
{{trans|C}} |
|||
<p>Debido a que los tipos básicos de Hopper son INT, LONG y DOUBLE, no es posible cumplir con la tarea en los términos específicos de ésta; sin embargo, sí es posible encontrar números "SUPER-D" teniendo en cuenta las limitaciones del coma-flotante, y calculando un poco más.</p> |
|||
<p>El coma flotante usado por Hopper garantiza que los primeros 16 dígitos de la parte entera son significativos (correctos), dejando a los restantes dígitos a la imaginación del computador. Esto me permite encontrar números SUPER-D cuyo "target" se encuentre dentro de los primeros 16 dígitos.</p> |
|||
<p>Si bien es cierto que la tarea requiere del uso de tipos BIG-INT, asumo que, habiendo encontrado algunos números, ésta está cumplida.</p> |
|||
<p>Para SUPER-9, es imposible encontrar números bajo las limitaciones de Hopper.</p> |
|||
<p>El resultado fue intervenido para resumir la aparición de los mensajes de error.</p> |
|||
<p> |
|||
Nota 1: los números grandes fueron comprobados (al menos, los primeros 16 dígitos), en la siguiente página: |
|||
</p> |
|||
<p>https://calculado.net/calculadora-de-numeros-grandes</p> |
|||
<p>Nota 2: por supuesto, algunos de los números desde SUPER-6 en adelante pueden ser incorrectos, porque se debe considerar el número completo como resultado real y correcto. Sin embargo, dudo que estén completamente erróneos, porque de lo contrario tendríamos un problema con el tipo DOUBLE y la confianza en los primeros 16 dígitos.</p><p>Dejo esta nota (2) aquí para su discusión ;) </p> |
|||
<syntaxhighlight lang="c"> |
|||
#include <basico.h> |
|||
algoritmo |
|||
decimales '0' |
|||
d=2 |
|||
ir a sub mientras ( #(d<=8), encontrar súperd ) |
|||
terminar |
|||
subrutinas |
|||
sub( encontrar súperd ) |
|||
imprimir("First 10 super-",d," numbers:\n") |
|||
count=0, j = 3.0, target="" |
|||
#(target = replicate( chr( 48 + d), d )) |
|||
iterar mientras ' #(count < 10) ' |
|||
cuando( #(occurs(target, string( (j^d) * d ))) ){ |
|||
si ( #( find(target,string( (j^d) * d ))<=16-d+1 ) ) |
|||
++count, #((j^d) * d ),";"#(int(j)),"\n", imprimir |
|||
sino |
|||
imprimir("Error by limited floating-point\n") |
|||
fin si |
|||
} |
|||
++j |
|||
reiterar |
|||
saltar |
|||
++d |
|||
retornar |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
$ hopper3 basica/superd.bas |
|||
First 10 super-2 numbers: |
|||
722;19 |
|||
1922;31 |
|||
9522;69 |
|||
13122;81 |
|||
22050;105 |
|||
22472;106 |
|||
22898;107 |
|||
28322;119 |
|||
32258;127 |
|||
34322;131 |
|||
First 10 super-3 numbers: |
|||
53338743;261 |
|||
295833384;462 |
|||
313461333;471 |
|||
333853923;481 |
|||
521223336;558 |
|||
1280873331;753 |
|||
3335803968;1036 |
|||
3433336008;1046 |
|||
9549030333;1471 |
|||
13354233375;1645 |
|||
First 10 super-4 numbers: |
|||
7444428488704;1168 |
|||
2444468646298624;4972 |
|||
12144449506652164;7423 |
|||
14444916891992064;7752 |
|||
20210466987444484;8431 |
|||
44446159394566080;10267 |
|||
65612298930444480;11317 |
|||
69644444001866240;11487 |
|||
71160258444475208;11549 |
|||
74444284887040000;11680 |
|||
First 10 super-5 numbers: |
|||
10320555555665840128;4602 |
|||
25555531873653735424;5517 |
|||
121769555550158815232;7539 |
|||
1824555552575530729472;12955 |
|||
3266111849055555420160;14555 |
|||
16555559203438988361728;20137 |
|||
17574555554247478345728;20379 |
|||
66949030555551289835520;26629 |
|||
289495555554740940046336;35689 |
|||
295053655555780915494912;35825 |
|||
First 10 super-6 numbers: |
|||
Error by limited floating-point (x7) |
|||
6886666667204071324753900265799680;323576 |
|||
110225436666664177977616958115282944;513675 |
|||
Error by limited floating-point (x2) |
|||
583566666663286739658021176443142144;678146 |
|||
Error by limited floating-point (x11) |
|||
75170784666666152681821170513110630400;1523993 |
|||
Error by limited floating-point (x3) |
|||
116749666666722233392107835976969093120;1640026 |
|||
Error by limited floating-point (x3) |
|||
176076108666666759379592167193103564800;1756271 |
|||
Error by limited floating-point (x2) |
|||
250899451666666024467063188536426496000;1863051 |
|||
Error by limited floating-point |
|||
266666617561594553577481823130432307200;1882072 |
|||
436901766666679373685701878627629531136;2043488 |
|||
Error by limited floating-point (x4) |
|||
666666906920386920350237344359883210752;2192601 |
|||
First 10 super-7 numbers: |
|||
Error by limited floating-point (x12) |
|||
177777775600462518614052285223994784063074336768;4258476 |
|||
Error by limited floating-point (x4) |
|||
993035700777777764170988126348947335750126403584;5444788 |
|||
Error by limited floating-point (x16) |
|||
46713777777797451604889330385832487876519153106944;9438581 |
|||
Error by limited floating-point (x3) |
|||
127977777771329971103305441414911647224808683339776;10900183 |
|||
Error by limited floating-point (x2) |
|||
185944035777777783325705920417758962467398899204096;11497728 |
|||
Error by limited floating-point (x6) |
|||
401493021777777721293822883896686959196909141491712;12834193 |
|||
Error by limited floating-point (x2) |
|||
620807777777080769345318482826386545204255464095744;13658671 |
|||
Error by limited floating-point (x3) |
|||
851802177777771784337179797881318978935678922915840;14290071 |
|||
Error by limited floating-point (x6) |
|||
1907267777777317249638349869607811168558639577300992;16034108 |
|||
1917295477777774148415418596878943250105383734214656;16046124 |
|||
First 10 super-8 numbers: |
|||
Error by limited floating-point (x8) |
|||
4277888888883959171581268707647711439890179731079492513300480;29242698 |
|||
Error by limited floating-point (x6) |
|||
98986718888888801286918789785886389895645834536018691101818880;43307276 |
|||
117888888882653975719110834321860851108606954628126584961236992;44263715 |
|||
Error by limited floating-point (x5) |
|||
627806888888889341739385231069597287624565300411183649261617152;54555936 |
|||
Error by limited floating-point (x7) |
|||
14888888883417818657923930639384765827471804545865401634268381184;81044125 |
|||
Error by limited floating-point (x20) |
|||
540888888884903246645687533027412939667041397478034734067117719552;126984952 |
|||
Error by limited floating-point (x2) |
|||
810999408888888833569602076936910583555158505247065293524113031168;133579963 |
|||
Error by limited floating-point (x8) |
|||
2326737888888882739301890030843707112889574955447311226724451090432;152390251 |
|||
Error by limited floating-point (x3) |
|||
2778888888871981007014152874201195401408300641311199300391968702464;155810833 |
|||
Error by limited floating-point (x19) |
|||
15111188888888925122195732008602567628522323430950253676602689847296;192542267 |
|||
(ESTOS VALORES SON COMPLETAMENTE ERRONEOS:) |
|||
First 10 super-9 numbers: |
|||
Error by limited floating-point |
|||
8999999999999999844710088704;1000 |
|||
4607999999999999920491565416448;2000 |
|||
177146999999999994896138025041920;3000 |
|||
2359295999999999959291681493221376;4000 |
|||
Error by limited floating-point |
|||
8999999999999999939063878597132419072;10000 |
|||
4607999999999999968800705841731798564864;20000 |
|||
2359295999999999984025961390966680865210368;40000 |
|||
Error by limited floating-point |
|||
.... |
|||
(ctrl-c) |
|||
$ |
|||
</pre> |
|||
=={{header|C sharp|C#}}== |
|||
===With / Without BigInteger=== |
|||
{{libheader|System.Numerics}} |
|||
Done three ways, two with BigIntegers, and one with a UIint64 structure. More details on the "Mostly addition" method on the discussion page. |
|||
<syntaxhighlight lang="csharp">using System; |
|||
using System.Collections.Generic; |
|||
using BI = System.Numerics.BigInteger; |
|||
using lbi = System.Collections.Generic.List<System.Numerics.BigInteger[]>; |
|||
using static System.Console; |
|||
class Program { |
|||
// provides 320 bits (90 decimal digits) |
|||
struct LI { public UInt64 lo, ml, mh, hi, tp; } |
|||
const UInt64 Lm = 1_000_000_000_000_000_000UL; |
|||
const string Fm = "D18"; |
|||
static void inc(ref LI d, LI s) { // d += s |
|||
d.lo += s.lo; while (d.lo >= Lm) { d.ml++; d.lo -= Lm; } |
|||
d.ml += s.ml; while (d.ml >= Lm) { d.mh++; d.ml -= Lm; } |
|||
d.mh += s.mh; while (d.mh >= Lm) { d.hi++; d.mh -= Lm; } |
|||
d.hi += s.hi; while (d.hi >= Lm) { d.tp++; d.hi -= Lm; } |
|||
d.tp += s.tp; |
|||
} |
|||
static void set(ref LI d, UInt64 s) { // d = s |
|||
d.lo = s; d.ml = d.mh = d.hi = d.tp = 0; |
|||
} |
|||
const int ls = 10; |
|||
static lbi co = new lbi { new BI[] { 0 } }; // for BigInteger addition |
|||
static List<LI[]> Co = new List<LI[]> { new LI[1] }; // for UInt64 addition |
|||
static Int64 ipow(Int64 bas, Int64 exp) { // Math.Pow() |
|||
Int64 res = 1; while (exp != 0) { |
|||
if ((exp & 1) != 0) res *= bas; exp >>= 1; bas *= bas; |
|||
} |
|||
return res; |
|||
} |
|||
// finishes up, shows performance value |
|||
static void fin() { WriteLine("{0}s", (DateTime.Now - st).TotalSeconds.ToString().Substring(0, 5)); } |
|||
static void funM(int d) { // straightforward BigInteger method, medium performance |
|||
string s = new string(d.ToString()[0], d); Write("{0}: ", d); |
|||
for (int i = 0, c = 0; c < ls; i++) |
|||
if ((BI.Pow((BI)i, d) * d).ToString().Contains(s)) |
|||
Write("{0} ", i, ++c); |
|||
fin(); |
|||
} |
|||
static void funS(int d) { // BigInteger "mostly adding" method, low performance |
|||
BI[] m = co[d]; |
|||
string s = new string(d.ToString()[0], d); Write("{0}: ", d); |
|||
for (int i = 0, c = 0; c < ls; i++) { |
|||
if ((d * m[0]).ToString().Contains(s)) |
|||
Write("{0} ", i, ++c); |
|||
for (int j = d, k = d - 1; j > 0; j = k--) m[k] += m[j]; |
|||
} |
|||
fin(); |
|||
} |
|||
static string scale(uint s, ref LI x) { // performs a small multiply and returns a string value |
|||
ulong Lo = x.lo * s, Ml = x.ml * s, Mh = x.mh * s, Hi = x.hi * s, Tp = x.tp * s; |
|||
while (Lo >= Lm) { Lo -= Lm; Ml++; } |
|||
while (Ml >= Lm) { Ml -= Lm; Mh++; } |
|||
while (Mh >= Lm) { Mh -= Lm; Hi++; } |
|||
while (Hi >= Lm) { Hi -= Lm; Tp++; } |
|||
if (Tp > 0) return Tp.ToString() + Hi.ToString(Fm) + Mh.ToString(Fm) + Ml.ToString(Fm) + Lo.ToString(Fm); |
|||
if (Hi > 0) return Hi.ToString() + Mh.ToString(Fm) + Ml.ToString(Fm) + Lo.ToString(Fm); |
|||
if (Mh > 0) return Mh.ToString() + Ml.ToString(Fm) + Lo.ToString(Fm); |
|||
if (Ml > 0) return Ml.ToString() + Lo.ToString(Fm); |
|||
return Lo.ToString(); |
|||
} |
|||
static void funF(int d) { // structure of UInt64 method, high performance |
|||
LI[] m = Co[d]; |
|||
string s = new string(d.ToString()[0], d); Write("{0}: ", d); |
|||
for (int i = d, c = 0; c < ls; i++) { |
|||
if (scale((uint)d, ref m[0]).Contains(s)) |
|||
Write("{0} ", i, ++c); |
|||
for (int j = d, k = d - 1; j > 0; j = k--) |
|||
inc(ref m[k], m[j]); |
|||
} |
|||
fin(); |
|||
} |
|||
static void init() { // initializes co and Co |
|||
for (int v = 1; v < 10; v++) { |
|||
BI[] res = new BI[v + 1]; |
|||
long[] f = new long[v + 1], l = new long[v + 1]; |
|||
for (int j = 0; j <= v; j++) { |
|||
if (j == v) { |
|||
LI[] t = new LI[v + 1]; |
|||
for (int y = 0; y <= v; y++) set(ref t[y], (UInt64)f[y]); |
|||
Co.Add(t); |
|||
} |
|||
res[j] = f[j]; |
|||
l[0] = f[0]; f[0] = ipow(j + 1, v); |
|||
for (int a = 0, b = 1; b <= v; a = b++) { |
|||
l[b] = f[b]; f[b] = f[a] - l[a]; |
|||
} |
|||
} |
|||
for (int z = res.Length - 2; z > 0; z -= 2) res[z] *= -1; |
|||
co.Add(res); |
|||
} |
|||
} |
|||
static DateTime st; |
|||
static void doOne(string title, int top, Action<int> func) { |
|||
WriteLine('\n' + title); st = DateTime.Now; |
|||
for (int i = 2; i <= top; i++) func(i); |
|||
} |
|||
static void Main(string[] args) |
|||
{ |
|||
init(); const int top = 9; |
|||
doOne("BigInteger mostly addition:", top, funS); |
|||
doOne("BigInteger.Pow():", top, funM); |
|||
doOne("UInt64 structure mostly addition:", top, funF); |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>BigInteger mostly addition: |
|||
2: 19 31 69 81 105 106 107 119 127 131 0.007s |
|||
3: 261 462 471 481 558 753 1036 1046 1471 1645 0.008s |
|||
4: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 0.014s |
|||
5: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 0.033s |
|||
6: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 0.584s |
|||
7: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 2.891s |
|||
8: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 20.47s |
|||
9: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 226.7s |
|||
BigInteger.Pow(): |
|||
2: 19 31 69 81 105 106 107 119 127 131 0.002s |
|||
3: 261 462 471 481 558 753 1036 1046 1471 1645 0.003s |
|||
4: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 0.008s |
|||
5: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 0.025s |
|||
6: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 0.450s |
|||
7: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 2.092s |
|||
8: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 14.80s |
|||
9: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 170.8s |
|||
UInt64 structure mostly addition: |
|||
2: 19 31 69 81 105 106 107 119 127 131 0.004s |
|||
3: 261 462 471 481 558 753 1036 1046 1471 1645 0.004s |
|||
4: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 0.006s |
|||
5: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 0.013s |
|||
6: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 0.188s |
|||
7: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 1.153s |
|||
8: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 9.783s |
|||
9: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 121.3s</pre> |
|||
Results from a core i7-7700 @ 3.6Ghz. The UInt64 structure method is quicker, but it's likely because the BigInteger.ToString() implementation in '''C#''' is so sluggish. I've ported this (UInt64 structure) algorithm to '''C++''', however it's quite a bit slower than the '''C++ GMP''' version. |
|||
Regarding the term "mostly addition", for this task there is some multiplication by a small integer (2 thru 9 in ''scale()''), but the powers of "n" are calculated by only addition. The initial tables are calculated with multiplication and a power function (''ipow()''). |
|||
=={{header|C}}== |
|||
{{libheader|GMP}} |
|||
<syntaxhighlight lang="c">#include <stdio.h> |
|||
#include <stdlib.h> |
|||
#include <string.h> |
|||
#include <gmp.h> |
|||
int main() { |
|||
for (unsigned int d = 2; d <= 9; ++d) { |
|||
printf("First 10 super-%u numbers:\n", d); |
|||
char digits[16] = { 0 }; |
|||
memset(digits, '0' + d, d); |
|||
mpz_t bignum; |
|||
mpz_init(bignum); |
|||
for (unsigned int count = 0, n = 1; count < 10; ++n) { |
|||
mpz_ui_pow_ui(bignum, n, d); |
|||
mpz_mul_ui(bignum, bignum, d); |
|||
char* str = mpz_get_str(NULL, 10, bignum); |
|||
if (strstr(str, digits)) { |
|||
printf("%u ", n); |
|||
++count; |
|||
} |
|||
free(str); |
|||
} |
|||
mpz_clear(bignum); |
|||
printf("\n"); |
|||
} |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 10 super-2 numbers: |
|||
19 31 69 81 105 106 107 119 127 131 |
|||
First 10 super-3 numbers: |
|||
261 462 471 481 558 753 1036 1046 1471 1645 |
|||
First 10 super-4 numbers: |
|||
1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
First 10 super-5 numbers: |
|||
4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
First 10 super-6 numbers: |
|||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
First 10 super-7 numbers: |
|||
140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 |
|||
First 10 super-8 numbers: |
|||
185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 |
|||
First 10 super-9 numbers: |
|||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
|||
</pre> |
|||
=={{header|C++}}== |
|||
{{trans|D}} |
|||
There are insufficiant bits avalaible to calculate the super-5 or super-6 numbers without a biginteger library |
|||
<syntaxhighlight lang="cpp">#include <iostream> |
|||
#include <sstream> |
|||
#include <vector> |
|||
uint64_t ipow(uint64_t base, uint64_t exp) { |
|||
uint64_t result = 1; |
|||
while (exp) { |
|||
if (exp & 1) { |
|||
result *= base; |
|||
} |
|||
exp >>= 1; |
|||
base *= base; |
|||
} |
|||
return result; |
|||
} |
|||
int main() { |
|||
using namespace std; |
|||
vector<string> rd{ "22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999" }; |
|||
for (uint64_t ii = 2; ii < 5; ii++) { |
|||
cout << "First 10 super-" << ii << " numbers:\n"; |
|||
int count = 0; |
|||
for (uint64_t j = 3; /* empty */; j++) { |
|||
auto k = ii * ipow(j, ii); |
|||
auto kstr = to_string(k); |
|||
auto needle = rd[(size_t)(ii - 2)]; |
|||
auto res = kstr.find(needle); |
|||
if (res != string::npos) { |
|||
count++; |
|||
cout << j << ' '; |
|||
if (count == 10) { |
|||
cout << "\n\n"; |
|||
break; |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return 0; |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>First 10 super-2 numbers: |
|||
19 31 69 81 105 106 107 119 127 131 |
|||
First 10 super-3 numbers: |
|||
261 462 471 481 558 753 1036 1046 1471 1645 |
|||
First 10 super-4 numbers: |
|||
1168 4972 7423 7752 8431 10267 11317 11487 11549 11680</pre> |
|||
===Alternative using GMP=== |
|||
{{libheader|GMP}} |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="cpp">#include <iostream> |
|||
#include <gmpxx.h> |
|||
using big_int = mpz_class; |
|||
int main() { |
|||
for (unsigned int d = 2; d <= 9; ++d) { |
|||
std::cout << "First 10 super-" << d << " numbers:\n"; |
|||
std::string digits(d, '0' + d); |
|||
big_int bignum; |
|||
for (unsigned int count = 0, n = 1; count < 10; ++n) { |
|||
mpz_ui_pow_ui(bignum.get_mpz_t(), n, d); |
|||
bignum *= d; |
|||
auto str(bignum.get_str()); |
|||
if (str.find(digits) != std::string::npos) { |
|||
std::cout << n << ' '; |
|||
++count; |
|||
} |
|||
} |
|||
std::cout << '\n'; |
|||
} |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 10 super-2 numbers: |
|||
19 31 69 81 105 106 107 119 127 131 |
|||
First 10 super-3 numbers: |
|||
261 462 471 481 558 753 1036 1046 1471 1645 |
|||
First 10 super-4 numbers: |
|||
1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
First 10 super-5 numbers: |
|||
4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
First 10 super-6 numbers: |
|||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
First 10 super-7 numbers: |
|||
140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 |
|||
First 10 super-8 numbers: |
|||
185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 |
|||
First 10 super-9 numbers: |
|||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
|||
</pre> |
|||
===Alternative ''not'' using GMP=== |
|||
{{trans|C#}} |
|||
<syntaxhighlight lang="cpp">#include <cstdio> |
|||
#include <sstream> |
|||
#include <chrono> |
|||
using namespace std; |
|||
using namespace chrono; |
|||
struct LI { uint64_t a, b, c, d, e; }; const uint64_t Lm = 1e18; |
|||
auto st = steady_clock::now(); LI k[10][10]; |
|||
string padZ(uint64_t x, int n = 18) { string r = to_string(x); |
|||
return string(max((int)(n - r.length()), 0), '0') + r; } |
|||
uint64_t ipow(uint64_t b, uint64_t e) { uint64_t r = 1; |
|||
while (e) { if (e & 1) r *= b; e >>= 1; b *= b; } return r; } |
|||
uint64_t fa(uint64_t x) { // factorial |
|||
uint64_t r = 1; while (x > 1) r *= x--; return r; } |
|||
void set(LI &d, uint64_t s) { // d = s |
|||
d.a = s; d.b = d.c = d.d = d.e = 0; } |
|||
void inc(LI &d, LI s) { // d += s |
|||
d.a += s.a; while (d.a >= Lm) { d.a -= Lm; d.b++; } |
|||
d.b += s.b; while (d.b >= Lm) { d.b -= Lm; d.c++; } |
|||
d.c += s.c; while (d.c >= Lm) { d.c -= Lm; d.d++; } |
|||
d.d += s.d; while (d.d >= Lm) { d.d -= Lm; d.e++; } |
|||
d.e += s.e; |
|||
} |
|||
string scale(uint32_t s, LI &x) { // multiplies x by s, converts to string |
|||
uint64_t A = x.a * s, B = x.b * s, C = x.c * s, D = x.d * s, E = x.e * s; |
|||
while (A >= Lm) { A -= Lm; B++; } |
|||
while (B >= Lm) { B -= Lm; C++; } |
|||
while (C >= Lm) { C -= Lm; D++; } |
|||
while (D >= Lm) { D -= Lm; E++; } |
|||
if (E > 0) return to_string(E) + padZ(D) + padZ(C) + padZ(B) + padZ(A); |
|||
if (D > 0) return to_string(D) + padZ(C) + padZ(B) + padZ(A); |
|||
if (C > 0) return to_string(C) + padZ(B) + padZ(A); |
|||
if (B > 0) return to_string(B) + padZ(A); |
|||
return to_string(A); |
|||
} |
|||
void fun(int d) { |
|||
auto m = k[d]; string s = string(d, '0' + d); printf("%d: ", d); |
|||
for (int i = d, c = 0; c < 10; i++) { |
|||
if (scale((uint32_t)d, m[0]).find(s) != string::npos) { |
|||
printf("%d ", i); ++c; } |
|||
for (int j = d, k = d - 1; j > 0; j = k--) inc(m[k], m[j]); |
|||
} printf("%ss\n", to_string(duration<double>(steady_clock::now() - st).count()).substr(0,5).c_str()); |
|||
} |
|||
static void init() { |
|||
for (int v = 1; v < 10; v++) { |
|||
uint64_t f[v + 1], l[v + 1]; |
|||
for (int j = 0; j <= v; j++) { |
|||
if (j == v) for (int y = 0; y <= v; y++) |
|||
set(k[v][y], v != y ? (uint64_t)f[y] : fa(v)); |
|||
l[0] = f[0]; f[0] = ipow(j + 1, v); |
|||
for (int a = 0, b = 1; b <= v; a = b++) { |
|||
l[b] = f[b]; f[b] = f[a] - l[a]; |
|||
} |
|||
} |
|||
} |
|||
} |
|||
int main() { |
|||
init(); |
|||
for (int i = 2; i <= 9; i++) fun(i); |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>2: 19 31 69 81 105 106 107 119 127 131 0.002s |
|||
3: 261 462 471 481 558 753 1036 1046 1471 1645 0.004s |
|||
4: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 0.009s |
|||
5: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 0.026s |
|||
6: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 0.399s |
|||
7: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 2.523s |
|||
8: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 22.32s |
|||
9: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 275.4s</pre> |
|||
Slower than '''GMP''' on the core i7-7700 @ 3.6Ghz, over twice as slow. This one is 275 seconds, vs. 102 seconds for '''GMP'''. |
|||
=={{header|Clojure}}== |
|||
{{trans|Raku}} |
|||
A more naïve implementation inspired by the Raku one, but without its use of parallelism; on my somewhat old and underpowered laptop, it gets through the basic task of 2 through 6 in about 6 seconds, then takes almost 40 to complete 7, and about six minutes for 8; with that growth rate, I didn't wait around for nine to complete. |
|||
<syntaxhighlight lang="clojure">(defn super [d] |
|||
(let [run (apply str (repeat d (str d)))] |
|||
(filter #(clojure.string/includes? (str (* d (Math/pow % d ))) run) (range)))) |
|||
(doseq [d (range 2 9)] |
|||
(println (str d ": ") (take 10 (super d))))</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>2: (19 31 69 81 105 106 107 119 127 131) |
|||
3: (261 462 471 558 753 1046 1471 1645 1752 1848) |
|||
4: (1168 4972 7423 7752 8431 11317 11487 11549 11680 16588) |
|||
5: (4602 5517 7539 9469 12955 14555 20137 20379 26629 35689) |
|||
6: (223763 302693 323576 513675 678146 1183741 1324944 1523993 1640026 1756271) |
|||
7: (4258476 9438581 10900183 11497728 12380285 12834193 13658671 14290071 16034108 16046124) |
|||
8: (29242698 43307276 44263715 45980752 54555936 81044125 126984952 133579963 142631696 152390251)</pre> |
|||
=={{header|D}}== |
|||
{{trans|Go}} |
|||
<syntaxhighlight lang="d">import std.bigint; |
|||
import std.conv; |
|||
import std.stdio; |
|||
import std.string; |
|||
void main() { |
|||
auto rd = ["22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999"]; |
|||
BigInt one = 1; |
|||
BigInt nine = 9; |
|||
for (int ii = 2; ii <= 9; ii++) { |
|||
writefln("First 10 super-%d numbers:", ii); |
|||
auto count = 0; |
|||
inner: |
|||
for (BigInt j = 3; ; j++) { |
|||
auto k = ii * j ^^ ii; |
|||
auto ix = k.to!string.indexOf(rd[ii-2]); |
|||
if (ix >= 0) { |
|||
count++; |
|||
write(j, ' '); |
|||
if (count == 10) { |
|||
writeln(); |
|||
writeln(); |
|||
break inner; |
|||
} |
|||
} |
|||
} |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>First 10 super-2 numbers: |
|||
19 31 69 81 105 106 107 119 127 131 |
|||
First 10 super-3 numbers: |
|||
261 462 471 481 558 753 1036 1046 1471 1645 |
|||
First 10 super-4 numbers: |
|||
1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
First 10 super-5 numbers: |
|||
4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
First 10 super-6 numbers: |
|||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
First 10 super-7 numbers: |
|||
140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 |
|||
First 10 super-8 numbers: |
|||
185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 |
|||
First 10 super-9 numbers: |
|||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181</pre> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
;The Function |
;The Function |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Generate Super-N numbers. Nigel Galloway: October 12th., 2019 |
// Generate Super-N numbers. Nigel Galloway: October 12th., 2019 |
||
let superD N= |
let superD N= |
||
Line 38: | Line 726: | ||
let rec fL n=match (E-n%I).IsZero with true->true |_->if (E*10I)<n then false else fL (n/10I) |
let rec fL n=match (E-n%I).IsZero with true->true |_->if (E*10I)<n then false else fL (n/10I) |
||
seq{1I..999999999999999999I}|>Seq.choose(fun n->if fL (G*n**N) then Some n else None) |
seq{1I..999999999999999999I}|>Seq.choose(fun n->if fL (G*n**N) then Some n else None) |
||
</syntaxhighlight> |
|||
</lang> |
|||
;The Task |
;The Task |
||
< |
<syntaxhighlight lang="fsharp"> |
||
superD 2 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn "" |
superD 2 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn "" |
||
superD 3 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn "" |
superD 3 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn "" |
||
Line 49: | Line 737: | ||
superD 8 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn "" |
superD 8 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn "" |
||
superD 9 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn "" |
superD 9 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn "" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 61: | Line 749: | ||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
||
</pre> |
</pre> |
||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: arrays formatting io kernel lists lists.lazy math |
||
math.functions math.ranges math.text.utils prettyprint sequences |
math.functions math.ranges math.text.utils prettyprint sequences |
||
; |
; |
||
Line 79: | Line 768: | ||
] with each ; |
] with each ; |
||
MAIN: super-d-demo</ |
MAIN: super-d-demo</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 97: | Line 786: | ||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
||
</pre> |
</pre> |
||
=={{header|FreeBASIC}}== |
|||
{{trans|Visual Basic .NET}} |
|||
<syntaxhighlight lang="vbnet">Dim rd(7) As String = {"22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999"} |
|||
For n As Integer = 2 To 9 |
|||
Dim cont As Integer = 0 |
|||
Dim j As Uinteger = 3 |
|||
Print Using !"\nFirst 10 super-# numbers:"; n |
|||
Do |
|||
Dim k As Ulongint = n * (j ^ n) |
|||
Dim ix As Uinteger = Instr(Str(k), rd(n - 2)) |
|||
If ix > 0 Then |
|||
cont += 1 |
|||
Print j; " " ; |
|||
End If |
|||
j += 1 |
|||
Loop Until cont = 10 |
|||
Next n</syntaxhighlight> |
|||
=={{header|Fōrmulæ}}== |
=={{header|Fōrmulæ}}== |
||
{{FormulaeEntry|page=https://formulae.org/?script=examples/Super-d_numbers}} |
|||
'''Solution''' |
|||
'''Case 1. Write a function/procedure/routine to find super-d numbers''' |
|||
[[File:Fōrmulæ - Super-d numbers 01.png]] |
|||
'''Case 2. For d=2 through d=9, use the routine to show the first 1 ssuper-d numbers''' |
|||
In [https://wiki.formulae.org/Super-d_numbers this] page you can see the solution of this task. |
|||
[[File:Fōrmulæ - Super-d numbers 02.png]] |
|||
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text ([http://wiki.formulae.org/Editing_F%C5%8Drmul%C3%A6_expressions more info]). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for transportation effects more than visualization and edition. |
|||
[[File:Fōrmulæ - Super-d numbers 03.png]] |
|||
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code. |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
Simple brute force approach and so not particularly quick - about 2.25 minutes on a Core i7. |
Simple brute force approach and so not particularly quick - about 2.25 minutes on a Core i7. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 142: | Line 858: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 178: | Line 894: | ||
found in 135616 ms |
found in 135616 ms |
||
</pre> |
</pre> |
||
=={{header|Haskell}}== |
|||
<syntaxhighlight lang="haskell">import Data.List (isInfixOf) |
|||
import Data.Char (intToDigit) |
|||
isSuperd :: (Show a, Integral a) => a -> a -> Bool |
|||
isSuperd p n = |
|||
(replicate <*> intToDigit) (fromIntegral p) `isInfixOf` show (p * n ^ p) |
|||
findSuperd :: (Show a, Integral a) => a -> [a] |
|||
findSuperd p = filter (isSuperd p) [1 ..] |
|||
main :: IO () |
|||
main = |
|||
mapM_ |
|||
(putStrLn . |
|||
("First 10 super-" ++) . |
|||
((++) . show <*> ((" : " ++) . show . take 10 . findSuperd))) |
|||
[2 .. 6]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 10 super-2 : [19,31,69,81,105,106,107,119,127,131] |
|||
First 10 super-3 : [261,462,471,481,558,753,1036,1046,1471,1645] |
|||
First 10 super-4 : [1168,4972,7423,7752,8431,10267,11317,11487,11549,11680] |
|||
First 10 super-5 : [4602,5517,7539,12955,14555,20137,20379,26629,32767,35689] |
|||
First 10 super-6 : [27257,272570,302693,323576,364509,502785,513675,537771,676657,678146] |
|||
</pre> |
|||
=={{header|J}}== |
|||
<pre> |
|||
superD=: 1 e. #~@[ E. 10 #.inv ([ * ^~)&x: |
|||
assert 3 superD 753 |
|||
assert -. 2 superD 753 |
|||
2 3 4 5 6 ,. _ 10 {. I. 2 3 4 5 6 superD&>/i.1e6 |
|||
2 19 31 69 81 105 106 107 119 127 131 |
|||
3 261 462 471 481 558 753 1036 1046 1471 1645 |
|||
4 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
5 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
6 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
</pre> |
|||
=={{header|Java}}== |
|||
<syntaxhighlight lang="java"> |
|||
import java.math.BigInteger; |
|||
public class SuperDNumbers { |
|||
public static void main(String[] args) { |
|||
for ( int i = 2 ; i <= 9 ; i++ ) { |
|||
superD(i, 10); |
|||
} |
|||
} |
|||
private static final void superD(int d, int max) { |
|||
long start = System.currentTimeMillis(); |
|||
String test = ""; |
|||
for ( int i = 0 ; i < d ; i++ ) { |
|||
test += (""+d); |
|||
} |
|||
int n = 0; |
|||
int i = 0; |
|||
System.out.printf("First %d super-%d numbers: %n", max, d); |
|||
while ( n < max ) { |
|||
i++; |
|||
BigInteger val = BigInteger.valueOf(d).multiply(BigInteger.valueOf(i).pow(d)); |
|||
if ( val.toString().contains(test) ) { |
|||
n++; |
|||
System.out.printf("%d ", i); |
|||
} |
|||
} |
|||
long end = System.currentTimeMillis(); |
|||
System.out.printf("%nRun time %d ms%n%n", end-start); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 10 super-2 numbers: |
|||
19 31 69 81 105 106 107 119 127 131 |
|||
Run time 6 ms |
|||
First 10 super-3 numbers: |
|||
261 462 471 481 558 753 1036 1046 1471 1645 |
|||
Run time 7 ms |
|||
First 10 super-4 numbers: |
|||
1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
Run time 13 ms |
|||
First 10 super-5 numbers: |
|||
4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
Run time 67 ms |
|||
First 10 super-6 numbers: |
|||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
Run time 546 ms |
|||
First 10 super-7 numbers: |
|||
140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 |
|||
Run time 2342 ms |
|||
First 10 super-8 numbers: |
|||
185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 |
|||
Run time 20545 ms |
|||
First 10 super-9 numbers: |
|||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
|||
Run time 268460 ms |
|||
</pre> |
|||
=={{header|jq}}== |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
The C implementation of jq does not have sufficiently accurate integer arithmetic to fulfill the task, |
|||
so the output shown below is based on a run of gojq. |
|||
<syntaxhighlight lang="jq"># To take advantage of gojq's arbitrary-precision integer arithmetic: |
|||
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in); |
|||
# Input is $d, the number of consecutive digits, 2 <= $d <= 9 |
|||
# $max is the number of superd numbers to be emitted. |
|||
def superd($number): |
|||
. as $d |
|||
| tostring as $s |
|||
| ($s * $d) as $target |
|||
| {count:0, j: 3 } |
|||
| while ( .count <= $number; |
|||
.emit = null |
|||
| if ((.j|power($d) * $d) | tostring) | index($target) |
|||
then .count += 1 |
|||
| .emit = .j |
|||
else . |
|||
end |
|||
| .j += 1 ) |
|||
| select(.emit).emit ; |
|||
# super-d for 2 <=d < 8 |
|||
range(2; 8) |
|||
| "First 10 super-\(.) numbers:", |
|||
superd(10)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 10 super-2 numbers: |
|||
19 |
|||
31 |
|||
69 |
|||
81 |
|||
105 |
|||
106 |
|||
107 |
|||
119 |
|||
127 |
|||
131 |
|||
First 10 super-3 numbers: |
|||
261 |
|||
462 |
|||
471 |
|||
481 |
|||
558 |
|||
753 |
|||
1036 |
|||
1046 |
|||
1471 |
|||
1645 |
|||
First 10 super-4 numbers: |
|||
1168 |
|||
4972 |
|||
7423 |
|||
7752 |
|||
8431 |
|||
10267 |
|||
11317 |
|||
11487 |
|||
11549 |
|||
11680 |
|||
First 10 super-5 numbers: |
|||
4602 |
|||
5517 |
|||
7539 |
|||
12955 |
|||
14555 |
|||
20137 |
|||
20379 |
|||
26629 |
|||
32767 |
|||
35689 |
|||
First 10 super-6 numbers: |
|||
27257 |
|||
272570 |
|||
302693 |
|||
323576 |
|||
364509 |
|||
502785 |
|||
513675 |
|||
537771 |
|||
676657 |
|||
678146 |
|||
First 10 super-7 numbers: |
|||
140997 |
|||
490996 |
|||
1184321 |
|||
1259609 |
|||
1409970 |
|||
1783166 |
|||
1886654 |
|||
1977538 |
|||
2457756 |
|||
2714763 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{trans|Phix}} |
{{trans|Phix}} |
||
< |
<syntaxhighlight lang="julia">function superd(N) |
||
println("First 10 super-$N numbers:") |
println("First 10 super-$N numbers:") |
||
count, j = 0, BigInt(3) |
count, j = 0, BigInt(3) |
||
Line 186: | Line 1,118: | ||
while count < 10 |
while count < 10 |
||
if occursin(target, string(j^N * N)) |
if occursin(target, string(j^N * N)) |
||
count +=1 |
count += 1 |
||
print("$j ") |
print("$j ") |
||
end |
end |
||
Line 194: | Line 1,126: | ||
end |
end |
||
for n in 2:9 |
|||
function testsuperd(imin, imax) |
|||
@time superd(n) |
|||
for n in imin:imax |
|||
@time superd(n) |
|||
end |
|||
end |
end |
||
</syntaxhighlight>{{out}} |
|||
testsuperd(2, 9) |
|||
</lang>{{out}} |
|||
<pre> |
<pre> |
||
First 10 super-2 numbers: |
First 10 super-2 numbers: |
||
Line 229: | Line 1,157: | ||
</pre> |
</pre> |
||
=={{header|Kotlin}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="scala">import java.math.BigInteger |
|||
fun superD(d: Int, max: Int) { |
|||
val start = System.currentTimeMillis() |
|||
var test = "" |
|||
for (i in 0 until d) { |
|||
test += d |
|||
} |
|||
var n = 0 |
|||
var i = 0 |
|||
println("First $max super-$d numbers:") |
|||
while (n < max) { |
|||
i++ |
|||
val value: Any = BigInteger.valueOf(d.toLong()) * BigInteger.valueOf(i.toLong()).pow(d) |
|||
if (value.toString().contains(test)) { |
|||
n++ |
|||
print("$i ") |
|||
} |
|||
} |
|||
val end = System.currentTimeMillis() |
|||
println("\nRun time ${end - start} ms\n") |
|||
} |
|||
fun main() { |
|||
for (i in 2..9) { |
|||
superD(i, 10) |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>First 10 super-2 numbers: |
|||
19 31 69 81 105 106 107 119 127 131 |
|||
Run time 31 ms |
|||
First 10 super-3 numbers: |
|||
261 462 471 481 558 753 1036 1046 1471 1645 |
|||
Run time 16 ms |
|||
First 10 super-4 numbers: |
|||
1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
Run time 25 ms |
|||
First 10 super-5 numbers: |
|||
4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
Run time 290 ms |
|||
First 10 super-6 numbers: |
|||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
Run time 1203 ms |
|||
First 10 super-7 numbers: |
|||
140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 |
|||
Run time 3876 ms |
|||
First 10 super-8 numbers: |
|||
185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 |
|||
Run time 29817 ms |
|||
First 10 super-9 numbers: |
|||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
|||
Run time 392181 ms</pre> |
|||
=={{header|Lua}}== |
|||
==={{header|Lua - using doubles}}=== |
|||
Lua's default numeric type is IEEE-754 doubles, which are insufficient beyond d=5, but for reference: |
|||
<syntaxhighlight lang="lua">for d = 2, 5 do |
|||
local n, found = 0, {} |
|||
local dds = string.rep(d, d) |
|||
while #found < 10 do |
|||
local dnd = string.format("%15.f", d * n ^ d) |
|||
if string.find(dnd, dds) then found[#found+1] = n end |
|||
n = n + 1 |
|||
end |
|||
print("super-" .. d .. ": " .. table.concat(found,", ")) |
|||
end</syntaxhighlight> |
|||
{{out}} |
|||
<pre>super-2: 19, 31, 69, 81, 105, 106, 107, 119, 127, 131 |
|||
super-3: 261, 462, 471, 481, 558, 753, 1036, 1046, 1471, 1645 |
|||
super-4: 1168, 4972, 7423, 7752, 8431, 10267, 11317, 11487, 11549, 11680 |
|||
super-5: 4602, 5517, 7539, 9469, 12955, 14555, 20137, 20379, 26629, 35689</pre> |
|||
==={{header|Lua - using lbc}}=== |
|||
Using the lbc library to provide support for arbitrary-precision integers, which are sufficient for both task and extra-credit: |
|||
<syntaxhighlight lang="lua">bc = require("bc") |
|||
for i = 2, 9 do |
|||
local d, n, found = bc.new(i), bc.new(0), {} |
|||
local dds = string.rep(d:tostring(), d:tonumber()) |
|||
while #found < 10 do |
|||
local dnd = (d * n ^ d):tostring() |
|||
if string.find(dnd, dds) then found[#found+1] = n:tostring() end |
|||
n = n + 1 |
|||
end |
|||
print("super-" .. d:tostring() .. ": " .. table.concat(found,", ")) |
|||
end</syntaxhighlight> |
|||
{{out}} |
|||
<pre>super-2: 19, 31, 69, 81, 105, 106, 107, 119, 127, 131 |
|||
super-3: 261, 462, 471, 481, 558, 753, 1036, 1046, 1471, 1645 |
|||
super-4: 1168, 4972, 7423, 7752, 8431, 10267, 11317, 11487, 11549, 11680 |
|||
super-5: 4602, 5517, 7539, 12955, 14555, 20137, 20379, 26629, 32767, 35689 |
|||
super-6: 27257, 272570, 302693, 323576, 364509, 502785, 513675, 537771, 676657, 678146 |
|||
super-7: 140997, 490996, 1184321, 1259609, 1409970, 1783166, 1886654, 1977538, 2457756, 2714763 |
|||
super-8: 185423, 641519, 1551728, 1854230, 6415190, 12043464, 12147605, 15517280, 16561735, 18542300 |
|||
super-9: 17546133, 32613656, 93568867, 107225764, 109255734, 113315082, 121251742, 175461330, 180917907, 182557181</pre> |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">ClearAll[SuperD] |
|||
SuperD[d_, m_] := Module[{n, res, num}, |
|||
res = {}; |
|||
n = 1; |
|||
While[Length[res] < m, |
|||
num = IntegerDigits[d n^d]; |
|||
If[MatchQ[num, {___, Repeated[d, {d}], ___}], |
|||
AppendTo[res, n] |
|||
]; |
|||
n++; |
|||
]; |
|||
res |
|||
] |
|||
Scan[Print[SuperD[#, 10]] &, Range[2, 6]]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>{19,31,69,81,105,106,107,119,127,131} |
|||
{261,462,471,481,558,753,1036,1046,1471,1645} |
|||
{1168,4972,7423,7752,8431,10267,11317,11487,11549,11680} |
|||
{4602,5517,7539,12955,14555,20137,20379,26629,32767,35689} |
|||
{27257,272570,302693,323576,364509,502785,513675,537771,676657,678146}</pre> |
|||
=={{header|Nim}}== |
|||
{{libheader|bignum}} |
|||
Using only the standard library, we would be limited to "d = 2, 3, 4". So, here is the program using the third-party library "bignum". |
|||
<syntaxhighlight lang="nim">import sequtils, strutils, times |
|||
import bignum |
|||
iterator superDNumbers(d, maxCount: Positive): Natural = |
|||
var count = 0 |
|||
var n = 2 |
|||
let e = culong(d) # Bignum ^ requires a culong as exponent. |
|||
let pattern = repeat(chr(d + ord('0')), d) |
|||
while count != maxCount: |
|||
if pattern in $(d * n ^ e): |
|||
yield n |
|||
inc count |
|||
inc n, 1 |
|||
let t0 = getTime() |
|||
for d in 2..9: |
|||
echo "First 10 super-$# numbers:".format(d) |
|||
echo toSeq(superDNumbers(d, 10)).join(" ") |
|||
echo "Time: ", getTime() - t0</syntaxhighlight> |
|||
{{out}} |
|||
<pre>First 10 super-2 numbers: |
|||
19 31 69 81 105 106 107 119 127 131 |
|||
First 10 super-3 numbers: |
|||
261 462 471 481 558 753 1036 1046 1471 1645 |
|||
First 10 super-4 numbers: |
|||
1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
First 10 super-5 numbers: |
|||
4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
First 10 super-6 numbers: |
|||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
First 10 super-7 numbers: |
|||
140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 |
|||
First 10 super-8 numbers: |
|||
185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 |
|||
First 10 super-9 numbers: |
|||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
|||
Time: 1 minute, 43 seconds, 647 milliseconds, 920 microseconds, and 938 nanoseconds</pre> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
{{works with|Free Pascal}} |
{{works with|Free Pascal}} |
||
gmp is fast.Same brute force as [http://rosettacode.org/wiki/Super-d_numbers#Go Go] |
gmp is fast.Same brute force as [http://rosettacode.org/wiki/Super-d_numbers#Go Go] |
||
< |
<syntaxhighlight lang="pascal">program Super_D; |
||
uses |
uses |
||
sysutils,gmp; |
sysutils,gmp; |
||
Line 271: | Line 1,368: | ||
end; |
end; |
||
mpz_clear(test); |
mpz_clear(test); |
||
End.</ |
End.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Finding 22 in 2*i**2 |
<pre>Finding 22 in 2*i**2 |
||
Line 305: | Line 1,402: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use bigint; |
use bigint; |
||
Line 326: | Line 1,423: | ||
} |
} |
||
say "\nFirst 10 super-$_ numbers:\n", join ' ', super($_) for 2..6;</ |
say "\nFirst 10 super-$_ numbers:\n", join ' ', super($_) for 2..6;</syntaxhighlight> |
||
<pre> |
<pre> |
||
Line 343: | Line 1,440: | ||
First 10 super-6 numbers: |
First 10 super-6 numbers: |
||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146</pre> |
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146</pre> |
||
=={{header|Perl 6}}== |
|||
{{works with|Rakudo|2019.07.1}} |
|||
2 - 6 take a few seconds, 7 about 17 seconds, 8 about 90... 9, bleh... around 700 seconds. |
|||
<lang perl6>sub super (\d) { |
|||
my \run = d x d; |
|||
^∞ .hyper.grep: -> \n { (d * n ** d).Str.contains: run } |
|||
} |
|||
(2..9).race(:1batch).map: { |
|||
my $now = now; |
|||
put "\nFirst 10 super-$_ numbers:\n{.&super[^10]}\n{(now - $now).round(.1)} sec." |
|||
}</lang> |
|||
<pre>First 10 super-2 numbers: |
|||
19 31 69 81 105 106 107 119 127 131 |
|||
0.1 sec. |
|||
First 10 super-3 numbers: |
|||
261 462 471 481 558 753 1036 1046 1471 1645 |
|||
0.1 sec. |
|||
First 10 super-4 numbers: |
|||
1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
0.3 sec. |
|||
First 10 super-5 numbers: |
|||
4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
0.6 sec. |
|||
First 10 super-6 numbers: |
|||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
5.2 sec. |
|||
First 10 super-7 numbers: |
|||
140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 |
|||
17.1 sec. |
|||
First 10 super-8 numbers: |
|||
185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 |
|||
92.1 sec. |
|||
First 10 super-9 numbers: |
|||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
|||
704.7 sec.</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>include mpfr.e |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
|||
procedure main() |
|||
atom t0 = time() |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
|||
mpz k = mpz_init() |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
for i=2 to 9 do |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span> |
|||
printf(1,"First 10 super-%d numbers:\n", i) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">7</span><span style="color: #0000FF;">:</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
integer count := 0, j = 3 |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"First 10 super-%d numbers:\n"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> |
|||
string tgt = repeat('0'+i,i) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span> |
|||
while count<10 do |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">tgt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">+</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> |
|||
mpz_ui_pow_ui(k,j,i) |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">count</span><span style="color: #0000FF;"><</span><span style="color: #000000;">10</span> <span style="color: #008080;">do</span> |
|||
mpz_mul_si(k,k,i) |
|||
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> |
|||
string s = mpz_get_str(k) |
|||
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> |
|||
integer ix = match(tgt,s) |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span> |
|||
if ix then |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">ix</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">match</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tgt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
count += 1 |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">ix</span> <span style="color: #008080;">then</span> |
|||
printf(1,"%d ", j) |
|||
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
end if |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d "</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">)</span> |
|||
j += 1 |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end while |
|||
<span style="color: #000000;">j</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
printf(1,"\nfound in %s\n\n", {elapsed(time()-t0)}) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
end for |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nfound in %s\n\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span> |
|||
end procedure |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
main()</lang> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 448: | Line 1,502: | ||
First 10 super-9 numbers: |
First 10 super-9 numbers: |
||
17546133 <killed> |
17546133 <killed> |
||
</pre> |
|||
Since its actually about 3 times faster under pwa/p2js, I let that one run, just the once, keeping the above capped at 7 for ~11s: |
|||
<pre> |
|||
... |
|||
First 10 super-8 numbers: |
|||
185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 |
|||
found in 1 minute and 22s |
|||
First 10 super-9 numbers: |
|||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
|||
found in 16 minutes and 6s |
|||
</pre> |
</pre> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Procedural=== |
|||
<lang python>from itertools import islice, count |
|||
<syntaxhighlight lang="python">from itertools import islice, count |
|||
def superd(d): |
def superd(d): |
||
Line 462: | Line 1,528: | ||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
for d in range(2, |
for d in range(2, 9): |
||
print(f"{d}:", ', '.join(str(n) for n in islice(superd(d), 10)))</ |
print(f"{d}:", ', '.join(str(n) for n in islice(superd(d), 10)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 473: | Line 1,539: | ||
7: 140997, 490996, 1184321, 1259609, 1409970, 1783166, 1886654, 1977538, 2457756, 2714763 |
7: 140997, 490996, 1184321, 1259609, 1409970, 1783166, 1886654, 1977538, 2457756, 2714763 |
||
8: 185423, 641519, 1551728, 1854230, 6415190, 12043464, 12147605, 15517280, 16561735, 18542300</pre> |
8: 185423, 641519, 1551728, 1854230, 6415190, 12043464, 12147605, 15517280, 16561735, 18542300</pre> |
||
===Functional=== |
|||
<syntaxhighlight lang="python">'''Super-d numbers''' |
|||
from itertools import count, islice |
|||
from functools import reduce |
|||
# ------------------------ SUPER-D ------------------------- |
|||
# super_d :: Int -> Either String [Int] |
|||
def super_d(d): |
|||
'''Either a message, if d is out of range, or |
|||
an infinite series of super_d numbers for d. |
|||
''' |
|||
if isinstance(d, int) and 1 < d < 10: |
|||
ds = d * str(d) |
|||
def p(x): |
|||
return ds in str(d * x ** d) |
|||
return Right(filter(p, count(2))) |
|||
else: |
|||
return Left( |
|||
'Super-d is defined only for integers drawn from {2..9}' |
|||
) |
|||
# ------------------------- TESTS -------------------------- |
|||
# main :: IO () |
|||
def main(): |
|||
'''Attempted sampling of first 10 values for d <- [1..6], |
|||
where d = 1 is out of range. |
|||
''' |
|||
for v in map( |
|||
lambda x: either( |
|||
append(str(x) + ' :: ') |
|||
)( |
|||
compose( |
|||
append('First 10 super-' + str(x) + ': '), |
|||
showList |
|||
) |
|||
)( |
|||
bindLR( |
|||
super_d(x) |
|||
)(compose(Right, take(10))) |
|||
), |
|||
enumFromTo(1)(6) |
|||
): print(v) |
|||
# ------------------------ GENERIC ------------------------- |
|||
# Left :: a -> Either a b |
|||
def Left(x): |
|||
'''Constructor for an empty Either (option type) value |
|||
with an associated string. |
|||
''' |
|||
return {'type': 'Either', 'Right': None, 'Left': x} |
|||
# Right :: b -> Either a b |
|||
def Right(x): |
|||
'''Constructor for a populated Either (option type) value''' |
|||
return {'type': 'Either', 'Left': None, 'Right': x} |
|||
# append (++) :: [a] -> [a] -> [a] |
|||
# append (++) :: String -> String -> String |
|||
def append(xs): |
|||
'''A list or string formed by |
|||
the concatenation of two others. |
|||
''' |
|||
def go(ys): |
|||
return xs + ys |
|||
return go |
|||
# bindLR (>>=) :: Either a -> (a -> Either b) -> Either b |
|||
def bindLR(m): |
|||
'''Either monad injection operator. |
|||
Two computations sequentially composed, |
|||
with any value produced by the first |
|||
passed as an argument to the second. |
|||
''' |
|||
def go(mf): |
|||
return ( |
|||
mf(m.get('Right')) if None is m.get('Left') else m |
|||
) |
|||
return go |
|||
# compose :: ((a -> a), ...) -> (a -> a) |
|||
def compose(*fs): |
|||
'''Composition, from right to left, |
|||
of a series of functions. |
|||
''' |
|||
def go(f, g): |
|||
def fg(x): |
|||
return f(g(x)) |
|||
return fg |
|||
return reduce(go, fs, lambda x: x) |
|||
# either :: (a -> c) -> (b -> c) -> Either a b -> c |
|||
def either(fl): |
|||
'''The application of fl to e if e is a Left value, |
|||
or the application of fr to e if e is a Right value. |
|||
''' |
|||
return lambda fr: lambda e: fl(e['Left']) if ( |
|||
None is e['Right'] |
|||
) else fr(e['Right']) |
|||
# enumFromTo :: Int -> Int -> [Int] |
|||
def enumFromTo(m): |
|||
'''Enumeration of integer values [m..n] |
|||
''' |
|||
return lambda n: range(m, 1 + n) |
|||
# showList :: [a] -> String |
|||
def showList(xs): |
|||
'''Stringification of a list.''' |
|||
return '[' + ','.join(str(x) for x in xs) + ']' |
|||
# take :: Int -> [a] -> [a] |
|||
# take :: Int -> String -> String |
|||
def take(n): |
|||
'''The prefix of xs of length n, |
|||
or xs itself if n > length xs. |
|||
''' |
|||
def go(xs): |
|||
return islice(xs, n) |
|||
return go |
|||
# MAIN --- |
|||
if __name__ == '__main__': |
|||
main()</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>1 :: Super-d is defined only for integers drawn from {2..9} |
|||
First 10 super-2: [19,31,69,81,105,106,107,119,127,131] |
|||
First 10 super-3: [261,462,471,481,558,753,1036,1046,1471,1645] |
|||
First 10 super-4: [1168,4972,7423,7752,8431,10267,11317,11487,11549,11680] |
|||
First 10 super-5: [4602,5517,7539,12955,14555,20137,20379,26629,32767,35689] |
|||
First 10 super-6: [27257,272570,302693,323576,364509,502785,513675,537771,676657,678146]</pre> |
|||
=={{header|Quackery}}== |
|||
<code>from</code>, <code>index</code> and <code>end</code> are defined at [[Loops/Increment loop index within loop body#Quackery]]. |
|||
<syntaxhighlight lang="Quackery"> [ over findseq swap found ] is hasseq ( [ x --> b ) |
|||
[ [] swap |
|||
[ 10 /mod |
|||
rot join swap |
|||
dup 0 = until ] |
|||
drop ] is digits ( n --> [ ) |
|||
[ over ** over * digits |
|||
swap dup of hasseq ] is superd ( n --> b ) |
|||
[] 5 times |
|||
[ [] 1 from |
|||
[ i^ 2 + index |
|||
superd if [ index join ] |
|||
dup size 10 = if end ] |
|||
nested join ] |
|||
witheach |
|||
[ i^ 2 + echo say " -> " echo cr ]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>2 -> [ 19 31 69 81 105 106 107 119 127 131 ] |
|||
3 -> [ 261 462 471 481 558 753 1036 1046 1471 1645 ] |
|||
4 -> [ 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 ] |
|||
5 -> [ 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 ] |
|||
6 -> [ 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 ] |
|||
</pre> |
|||
=={{header|R}}== |
|||
{{libheader|Rmpfr}} |
|||
Library is necessary to go beyond super-4 numbers. Indeed [https://cran.r-project.org/web/packages/Rmpfr/Rmpfr.pdf Rmpfr] allows to augment precision for floating point numbers. I didn't go for extra task, because it took some minutes for super-6 numbers. |
|||
<syntaxhighlight lang="r">library(Rmpfr) |
|||
options(scipen = 999) |
|||
find_super_d_number <- function(d, N = 10){ |
|||
super_number <- c(NA) |
|||
n = 0 |
|||
n_found = 0 |
|||
while(length(super_number) < N){ |
|||
n = n + 1 |
|||
test = d * mpfr(n, precBits = 200) ** d #Here I augment precision |
|||
test_formatted = .mpfr2str(test)$str #and I extract the string from S4 class object |
|||
iterable = strsplit(test_formatted, "")[[1]] |
|||
if (length(iterable) < d) next |
|||
for(i in d:length(iterable)){ |
|||
if (iterable[i] != d) next |
|||
equalities = 0 |
|||
for(j in 1:d) { |
|||
if (i == j) break |
|||
if(iterable[i] == iterable[i-j]) |
|||
equalities = equalities + 1 |
|||
else break |
|||
} |
|||
if (equalities >= (d-1)) { |
|||
n_found = n_found + 1 |
|||
super_number[n_found] = n |
|||
break |
|||
} |
|||
} |
|||
} |
|||
message(paste0("First ", N, " super-", d, " numbers:")) |
|||
print((super_number)) |
|||
return(super_number) |
|||
} |
|||
for(d in 2:6){find_super_d_number(d, N = 10)} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 10 super-2 numbers: |
|||
[1] 19 31 69 81 105 106 107 119 127 131 |
|||
First 10 super-3 numbers: |
|||
[1] 261 462 471 481 558 753 1036 1046 1471 1645 |
|||
First 10 super-4 numbers: |
|||
[1] 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
First 10 super-5 numbers: |
|||
[1] 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
First 10 super-6 numbers: |
|||
[1] 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
</pre> |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{works with|Rakudo|2019.07.1}} |
|||
2 - 6 take a few seconds, 7 about 17 seconds, 8 about 90... 9, bleh... around 700 seconds. |
|||
<syntaxhighlight lang="raku" line>sub super (\d) { |
|||
my \run = d x d; |
|||
^∞ .hyper.grep: -> \n { (d * n ** d).Str.contains: run } |
|||
} |
|||
(2..9).race(:1batch).map: { |
|||
my $now = now; |
|||
put "\nFirst 10 super-$_ numbers:\n{.&super[^10]}\n{(now - $now).round(.1)} sec." |
|||
}</syntaxhighlight> |
|||
<pre>First 10 super-2 numbers: |
|||
19 31 69 81 105 106 107 119 127 131 |
|||
0.1 sec. |
|||
First 10 super-3 numbers: |
|||
261 462 471 481 558 753 1036 1046 1471 1645 |
|||
0.1 sec. |
|||
First 10 super-4 numbers: |
|||
1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
0.3 sec. |
|||
First 10 super-5 numbers: |
|||
4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
0.6 sec. |
|||
First 10 super-6 numbers: |
|||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
5.2 sec. |
|||
First 10 super-7 numbers: |
|||
140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 |
|||
17.1 sec. |
|||
First 10 super-8 numbers: |
|||
185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 |
|||
92.1 sec. |
|||
First 10 super-9 numbers: |
|||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
|||
704.7 sec.</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight lang="rexx">/*REXX program computes and displays the first N super─d numbers for D from LO to HI.*/ |
||
numeric digits 100 /*ensure enough decimal digs for calc. */ |
numeric digits 100 /*ensure enough decimal digs for calc. */ |
||
parse arg n LO HI . /*obtain optional arguments from the CL*/ |
parse arg n LO HI . /*obtain optional arguments from the CL*/ |
||
Line 486: | Line 1,847: | ||
do j=2 until #==n /*search for super─d numbers 'til found*/ |
do j=2 until #==n /*search for super─d numbers 'til found*/ |
||
if pos(z, d * j**d)==0 then iterate /*does product have the required reps? */ |
if pos(z, d * j**d)==0 then iterate /*does product have the required reps? */ |
||
#= # + 1; |
#= # + 1; $= $ j /*bump counter; add the number to list*/ |
||
end /*j*/ |
end /*j*/ |
||
say |
say |
||
say center(' the first ' n " super-"d 'numbers ', digits(), "═") |
say center(' the first ' n " super-"d 'numbers ', digits(), "═") |
||
say $ |
say $ |
||
end /*d*/ /*stick a fork in it, we're all done. */</ |
end /*d*/ /*stick a fork in it, we're all done. */</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 517: | Line 1,878: | ||
══════════════════════════════════ the first 10 super-9 numbers ══════════════════════════════════ |
══════════════════════════════════ the first 10 super-9 numbers ══════════════════════════════════ |
||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
||
</pre> |
|||
=={{header|Ruby}}== |
|||
<syntaxhighlight lang="ruby">(2..8).each do |d| |
|||
rep = d.to_s * d |
|||
print "#{d}: " |
|||
puts (2..).lazy.select{|n| (d * n**d).to_s.include?(rep) }.first(10).join(", ") |
|||
end |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>2: 19, 31, 69, 81, 105, 106, 107, 119, 127, 131 |
|||
3: 261, 462, 471, 481, 558, 753, 1036, 1046, 1471, 1645 |
|||
4: 1168, 4972, 7423, 7752, 8431, 10267, 11317, 11487, 11549, 11680 |
|||
5: 4602, 5517, 7539, 12955, 14555, 20137, 20379, 26629, 32767, 35689 |
|||
6: 27257, 272570, 302693, 323576, 364509, 502785, 513675, 537771, 676657, 678146 |
|||
7: 140997, 490996, 1184321, 1259609, 1409970, 1783166, 1886654, 1977538, 2457756, 2714763 |
|||
8: 185423, 641519, 1551728, 1854230, 6415190, 12043464, 12147605, 15517280, 16561735, 18542300 |
|||
</pre> |
|||
The first 10 super_9 numbers (not shown) take about 540 seconds. |
|||
=={{header|Rust}}== |
|||
<syntaxhighlight lang="rust">// [dependencies] |
|||
// rug = "1.9" |
|||
fn print_super_d_numbers(d: u32, limit: u32) { |
|||
use rug::Assign; |
|||
use rug::Integer; |
|||
println!("First {} super-{} numbers:", limit, d); |
|||
let digits = d.to_string().repeat(d as usize); |
|||
let mut count = 0; |
|||
let mut n = 1; |
|||
let mut s = Integer::new(); |
|||
while count < limit { |
|||
s.assign(Integer::u_pow_u(n, d)); |
|||
s *= d; |
|||
if s.to_string().contains(&digits) { |
|||
print!("{} ", n); |
|||
count += 1; |
|||
} |
|||
n += 1; |
|||
} |
|||
println!(); |
|||
} |
|||
fn main() { |
|||
for d in 2..=9 { |
|||
print_super_d_numbers(d, 10); |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 10 super-2 numbers: |
|||
19 31 69 81 105 106 107 119 127 131 |
|||
First 10 super-3 numbers: |
|||
261 462 471 481 558 753 1036 1046 1471 1645 |
|||
First 10 super-4 numbers: |
|||
1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
First 10 super-5 numbers: |
|||
4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
First 10 super-6 numbers: |
|||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
First 10 super-7 numbers: |
|||
140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 |
|||
First 10 super-8 numbers: |
|||
185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 |
|||
First 10 super-9 numbers: |
|||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
|||
</pre> |
|||
=={{header|Sidef}}== |
|||
<syntaxhighlight lang="ruby">func super_d(d) { |
|||
var D = Str(d)*d |
|||
1..Inf -> lazy.grep {|n| Str(d * n**d).contains(D) } |
|||
} |
|||
for d in (2..8) { |
|||
say ("#{d}: ", super_d(d).first(10)) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
2: [19, 31, 69, 81, 105, 106, 107, 119, 127, 131] |
|||
3: [261, 462, 471, 481, 558, 753, 1036, 1046, 1471, 1645] |
|||
4: [1168, 4972, 7423, 7752, 8431, 10267, 11317, 11487, 11549, 11680] |
|||
5: [4602, 5517, 7539, 12955, 14555, 20137, 20379, 26629, 32767, 35689] |
|||
6: [27257, 272570, 302693, 323576, 364509, 502785, 513675, 537771, 676657, 678146] |
|||
7: [140997, 490996, 1184321, 1259609, 1409970, 1783166, 1886654, 1977538, 2457756, 2714763] |
|||
8: [185423, 641519, 1551728, 1854230, 6415190, 12043464, 12147605, 15517280, 16561735, 18542300] |
|||
</pre> |
|||
=={{header|Swift}}== |
|||
{{libheader|AttaSwift BigInt}} |
|||
<syntaxhighlight lang="swift">import BigInt |
|||
import Foundation |
|||
let rd = ["22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999"] |
|||
for d in 2...9 { |
|||
print("First 10 super-\(d) numbers:") |
|||
var count = 0 |
|||
var n = BigInt(3) |
|||
var k = BigInt(0) |
|||
while true { |
|||
k = n.power(d) |
|||
k *= BigInt(d) |
|||
if let _ = String(k).range(of: rd[d - 2]) { |
|||
count += 1 |
|||
print(n, terminator: " ") |
|||
fflush(stdout) |
|||
guard count < 10 else { |
|||
break |
|||
} |
|||
} |
|||
n += 1 |
|||
} |
|||
print() |
|||
print() |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>First 10 super-2 numbers: |
|||
19 31 69 81 105 106 107 119 127 131 |
|||
First 10 super-3 numbers: |
|||
261 462 471 481 558 753 1036 1046 1471 1645 |
|||
First 10 super-4 numbers: |
|||
1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
First 10 super-5 numbers: |
|||
4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
First 10 super-6 numbers: |
|||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
First 10 super-7 numbers: |
|||
140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 |
|||
First 10 super-8 numbers: |
|||
185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 |
|||
First 10 super-9 numbers: |
|||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181</pre> |
|||
=={{header|Visual Basic .NET}}== |
|||
{{trans|D}} |
|||
<syntaxhighlight lang="vbnet">Imports System.Numerics |
|||
Module Module1 |
|||
Sub Main() |
|||
Dim rd = {"22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999"} |
|||
Dim one As BigInteger = 1 |
|||
Dim nine As BigInteger = 9 |
|||
For ii = 2 To 9 |
|||
Console.WriteLine("First 10 super-{0} numbers:", ii) |
|||
Dim count = 0 |
|||
Dim j As BigInteger = 3 |
|||
While True |
|||
Dim k = ii * BigInteger.Pow(j, ii) |
|||
Dim ix = k.ToString.IndexOf(rd(ii - 2)) |
|||
If ix >= 0 Then |
|||
count += 1 |
|||
Console.Write("{0} ", j) |
|||
If count = 10 Then |
|||
Console.WriteLine() |
|||
Console.WriteLine() |
|||
Exit While |
|||
End If |
|||
End If |
|||
j += 1 |
|||
End While |
|||
Next |
|||
End Sub |
|||
End Module</syntaxhighlight> |
|||
{{out}} |
|||
<pre>First 10 super-2 numbers: |
|||
19 31 69 81 105 106 107 119 127 131 |
|||
First 10 super-3 numbers: |
|||
261 462 471 481 558 753 1036 1046 1471 1645 |
|||
First 10 super-4 numbers: |
|||
1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
First 10 super-5 numbers: |
|||
4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
First 10 super-6 numbers: |
|||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
First 10 super-7 numbers: |
|||
140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 |
|||
First 10 super-8 numbers: |
|||
185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 |
|||
First 10 super-9 numbers: |
|||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181</pre> |
|||
=={{header|Wren}}== |
|||
{{trans|Go}} |
|||
===CLI (BigInt)=== |
|||
{{libheader|Wren-big}} |
|||
{{libheader|Wren-fmt}} |
|||
Managed to get up to 8 but too slow for 9. |
|||
<syntaxhighlight lang="wren">import "./big" for BigInt |
|||
import "./fmt" for Fmt |
|||
var start = System.clock |
|||
var rd = ["22", "333", "4444", "55555", "666666", "7777777", "88888888"] |
|||
for (i in 2..8) { |
|||
Fmt.print("First 10 super-$d numbers:", i) |
|||
var count = 0 |
|||
var j = BigInt.three |
|||
while (true) { |
|||
var k = j.pow(i) * i |
|||
var ix = k.toString.indexOf(rd[i-2]) |
|||
if (ix >= 0) { |
|||
count = count + 1 |
|||
Fmt.write("$i ", j) |
|||
if (count == 10) { |
|||
Fmt.print("\nfound in $f seconds\n", System.clock - start) |
|||
break |
|||
} |
|||
} |
|||
j = j.inc |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 10 super-2 numbers: |
|||
19 31 69 81 105 106 107 119 127 131 |
|||
found in 0.000500 seconds |
|||
First 10 super-3 numbers: |
|||
261 462 471 481 558 753 1036 1046 1471 1645 |
|||
found in 0.007636 seconds |
|||
First 10 super-4 numbers: |
|||
1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
found in 0.070462 seconds |
|||
First 10 super-5 numbers: |
|||
4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
found in 0.388554 seconds |
|||
First 10 super-6 numbers: |
|||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
found in 10.044345 seconds |
|||
First 10 super-7 numbers: |
|||
140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 |
|||
found in 62.021899 seconds |
|||
First 10 super-8 numbers: |
|||
185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 |
|||
found in 434.536825 seconds |
|||
</pre> |
|||
===Embedded (GMP)=== |
|||
{{libheader|Wren-gmp}} |
|||
Much sprightlier with 8 now being reached in 11.7 seconds and 9 in 126.5 seconds. |
|||
<syntaxhighlight lang="wren">/* Super-d_numbers_2.wren */ |
|||
import "./gmp" for Mpz |
|||
import "./fmt" for Fmt |
|||
var start = System.clock |
|||
var rd = ["22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999"] |
|||
for (i in 2..9) { |
|||
Fmt.print("First 10 super-$d numbers:", i) |
|||
var count = 0 |
|||
var j = Mpz.three |
|||
var k = Mpz.new() |
|||
while (true) { |
|||
k.pow(j, i).mul(i) |
|||
var ix = k.toString.indexOf(rd[i-2]) |
|||
if (ix >= 0) { |
|||
count = count + 1 |
|||
Fmt.write("$i ", j) |
|||
if (count == 10) { |
|||
Fmt.print("\nfound in $f seconds\n", System.clock - start) |
|||
break |
|||
} |
|||
} |
|||
j.inc |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 10 super-2 numbers: |
|||
19 31 69 81 105 106 107 119 127 131 |
|||
found in 0.000222 seconds |
|||
First 10 super-3 numbers: |
|||
261 462 471 481 558 753 1036 1046 1471 1645 |
|||
found in 0.001222 seconds |
|||
First 10 super-4 numbers: |
|||
1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 |
|||
found in 0.007386 seconds |
|||
First 10 super-5 numbers: |
|||
4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 |
|||
found in 0.024863 seconds |
|||
First 10 super-6 numbers: |
|||
27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 |
|||
found in 0.339837 seconds |
|||
First 10 super-7 numbers: |
|||
140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 |
|||
found in 1.684412 seconds |
|||
First 10 super-8 numbers: |
|||
185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 |
|||
found in 11.695570 seconds |
|||
First 10 super-9 numbers: |
|||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
|||
found in 126.454911 seconds |
|||
</pre> |
</pre> |
||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library |
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library |
||
< |
<syntaxhighlight lang="zkl">var [const] BI=Import("zklBigNum"); // libGMP |
||
fcn superDW(d){ |
fcn superDW(d){ |
||
Line 528: | Line 2,228: | ||
{ BI(n).pow(d).mul(d).toString().holds(digits) and n or Void.Skip }); |
{ BI(n).pow(d).mul(d).toString().holds(digits) and n or Void.Skip }); |
||
} |
} |
||
foreach d in ([2..8]){ println(d," : ",superDW(d).walk(10).concat(" ")) }</ |
foreach d in ([2..8]){ println(d," : ",superDW(d).walk(10).concat(" ")) }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Latest revision as of 22:41, 27 February 2024
You are encouraged to solve this task according to the task description, using any language you may know.
A super-d number is a positive, decimal (base ten) integer n such that d × nd has at least d consecutive digits d where
2 ≤ d ≤ 9
For instance, 753 is a super-3 number because 3 × 7533 = 1280873331.
Super-d numbers are also shown on MathWorld™ as super-d or super-d.
- Task
-
- Write a function/procedure/routine to find super-d numbers.
- For d=2 through d=6, use the routine to show the first 10 super-d numbers.
- Extra credit
-
- Show the first 10 super-7, super-8, and/or super-9 numbers (optional).
11l
V rd = [‘22’, ‘333’, ‘4444’, ‘55555’, ‘666666’, ‘7777777’, ‘88888888’, ‘999999999’]
L(ii) 2..7
print(‘First 10 super-#. numbers:’.format(ii))
V count = 0
BigInt j = 3
L
V k = ii * j^ii
I rd[ii - 2] C String(k)
count++
print(j, end' ‘ ’)
I count == 10
print("\n")
L.break
j++
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763
Amazing Hopper
Debido a que los tipos básicos de Hopper son INT, LONG y DOUBLE, no es posible cumplir con la tarea en los términos específicos de ésta; sin embargo, sí es posible encontrar números "SUPER-D" teniendo en cuenta las limitaciones del coma-flotante, y calculando un poco más.
El coma flotante usado por Hopper garantiza que los primeros 16 dígitos de la parte entera son significativos (correctos), dejando a los restantes dígitos a la imaginación del computador. Esto me permite encontrar números SUPER-D cuyo "target" se encuentre dentro de los primeros 16 dígitos.
Si bien es cierto que la tarea requiere del uso de tipos BIG-INT, asumo que, habiendo encontrado algunos números, ésta está cumplida.
Para SUPER-9, es imposible encontrar números bajo las limitaciones de Hopper.
El resultado fue intervenido para resumir la aparición de los mensajes de error.
Nota 1: los números grandes fueron comprobados (al menos, los primeros 16 dígitos), en la siguiente página:
https://calculado.net/calculadora-de-numeros-grandes
Nota 2: por supuesto, algunos de los números desde SUPER-6 en adelante pueden ser incorrectos, porque se debe considerar el número completo como resultado real y correcto. Sin embargo, dudo que estén completamente erróneos, porque de lo contrario tendríamos un problema con el tipo DOUBLE y la confianza en los primeros 16 dígitos.
Dejo esta nota (2) aquí para su discusión ;)
#include <basico.h>
algoritmo
decimales '0'
d=2
ir a sub mientras ( #(d<=8), encontrar súperd )
terminar
subrutinas
sub( encontrar súperd )
imprimir("First 10 super-",d," numbers:\n")
count=0, j = 3.0, target=""
#(target = replicate( chr( 48 + d), d ))
iterar mientras ' #(count < 10) '
cuando( #(occurs(target, string( (j^d) * d ))) ){
si ( #( find(target,string( (j^d) * d ))<=16-d+1 ) )
++count, #((j^d) * d ),";"#(int(j)),"\n", imprimir
sino
imprimir("Error by limited floating-point\n")
fin si
}
++j
reiterar
saltar
++d
retornar
- Output:
$ hopper3 basica/superd.bas First 10 super-2 numbers: 722;19 1922;31 9522;69 13122;81 22050;105 22472;106 22898;107 28322;119 32258;127 34322;131 First 10 super-3 numbers: 53338743;261 295833384;462 313461333;471 333853923;481 521223336;558 1280873331;753 3335803968;1036 3433336008;1046 9549030333;1471 13354233375;1645 First 10 super-4 numbers: 7444428488704;1168 2444468646298624;4972 12144449506652164;7423 14444916891992064;7752 20210466987444484;8431 44446159394566080;10267 65612298930444480;11317 69644444001866240;11487 71160258444475208;11549 74444284887040000;11680 First 10 super-5 numbers: 10320555555665840128;4602 25555531873653735424;5517 121769555550158815232;7539 1824555552575530729472;12955 3266111849055555420160;14555 16555559203438988361728;20137 17574555554247478345728;20379 66949030555551289835520;26629 289495555554740940046336;35689 295053655555780915494912;35825 First 10 super-6 numbers: Error by limited floating-point (x7) 6886666667204071324753900265799680;323576 110225436666664177977616958115282944;513675 Error by limited floating-point (x2) 583566666663286739658021176443142144;678146 Error by limited floating-point (x11) 75170784666666152681821170513110630400;1523993 Error by limited floating-point (x3) 116749666666722233392107835976969093120;1640026 Error by limited floating-point (x3) 176076108666666759379592167193103564800;1756271 Error by limited floating-point (x2) 250899451666666024467063188536426496000;1863051 Error by limited floating-point 266666617561594553577481823130432307200;1882072 436901766666679373685701878627629531136;2043488 Error by limited floating-point (x4) 666666906920386920350237344359883210752;2192601 First 10 super-7 numbers: Error by limited floating-point (x12) 177777775600462518614052285223994784063074336768;4258476 Error by limited floating-point (x4) 993035700777777764170988126348947335750126403584;5444788 Error by limited floating-point (x16) 46713777777797451604889330385832487876519153106944;9438581 Error by limited floating-point (x3) 127977777771329971103305441414911647224808683339776;10900183 Error by limited floating-point (x2) 185944035777777783325705920417758962467398899204096;11497728 Error by limited floating-point (x6) 401493021777777721293822883896686959196909141491712;12834193 Error by limited floating-point (x2) 620807777777080769345318482826386545204255464095744;13658671 Error by limited floating-point (x3) 851802177777771784337179797881318978935678922915840;14290071 Error by limited floating-point (x6) 1907267777777317249638349869607811168558639577300992;16034108 1917295477777774148415418596878943250105383734214656;16046124 First 10 super-8 numbers: Error by limited floating-point (x8) 4277888888883959171581268707647711439890179731079492513300480;29242698 Error by limited floating-point (x6) 98986718888888801286918789785886389895645834536018691101818880;43307276 117888888882653975719110834321860851108606954628126584961236992;44263715 Error by limited floating-point (x5) 627806888888889341739385231069597287624565300411183649261617152;54555936 Error by limited floating-point (x7) 14888888883417818657923930639384765827471804545865401634268381184;81044125 Error by limited floating-point (x20) 540888888884903246645687533027412939667041397478034734067117719552;126984952 Error by limited floating-point (x2) 810999408888888833569602076936910583555158505247065293524113031168;133579963 Error by limited floating-point (x8) 2326737888888882739301890030843707112889574955447311226724451090432;152390251 Error by limited floating-point (x3) 2778888888871981007014152874201195401408300641311199300391968702464;155810833 Error by limited floating-point (x19) 15111188888888925122195732008602567628522323430950253676602689847296;192542267 (ESTOS VALORES SON COMPLETAMENTE ERRONEOS:) First 10 super-9 numbers: Error by limited floating-point 8999999999999999844710088704;1000 4607999999999999920491565416448;2000 177146999999999994896138025041920;3000 2359295999999999959291681493221376;4000 Error by limited floating-point 8999999999999999939063878597132419072;10000 4607999999999999968800705841731798564864;20000 2359295999999999984025961390966680865210368;40000 Error by limited floating-point .... (ctrl-c) $
C#
With / Without BigInteger
Done three ways, two with BigIntegers, and one with a UIint64 structure. More details on the "Mostly addition" method on the discussion page.
using System;
using System.Collections.Generic;
using BI = System.Numerics.BigInteger;
using lbi = System.Collections.Generic.List<System.Numerics.BigInteger[]>;
using static System.Console;
class Program {
// provides 320 bits (90 decimal digits)
struct LI { public UInt64 lo, ml, mh, hi, tp; }
const UInt64 Lm = 1_000_000_000_000_000_000UL;
const string Fm = "D18";
static void inc(ref LI d, LI s) { // d += s
d.lo += s.lo; while (d.lo >= Lm) { d.ml++; d.lo -= Lm; }
d.ml += s.ml; while (d.ml >= Lm) { d.mh++; d.ml -= Lm; }
d.mh += s.mh; while (d.mh >= Lm) { d.hi++; d.mh -= Lm; }
d.hi += s.hi; while (d.hi >= Lm) { d.tp++; d.hi -= Lm; }
d.tp += s.tp;
}
static void set(ref LI d, UInt64 s) { // d = s
d.lo = s; d.ml = d.mh = d.hi = d.tp = 0;
}
const int ls = 10;
static lbi co = new lbi { new BI[] { 0 } }; // for BigInteger addition
static List<LI[]> Co = new List<LI[]> { new LI[1] }; // for UInt64 addition
static Int64 ipow(Int64 bas, Int64 exp) { // Math.Pow()
Int64 res = 1; while (exp != 0) {
if ((exp & 1) != 0) res *= bas; exp >>= 1; bas *= bas;
}
return res;
}
// finishes up, shows performance value
static void fin() { WriteLine("{0}s", (DateTime.Now - st).TotalSeconds.ToString().Substring(0, 5)); }
static void funM(int d) { // straightforward BigInteger method, medium performance
string s = new string(d.ToString()[0], d); Write("{0}: ", d);
for (int i = 0, c = 0; c < ls; i++)
if ((BI.Pow((BI)i, d) * d).ToString().Contains(s))
Write("{0} ", i, ++c);
fin();
}
static void funS(int d) { // BigInteger "mostly adding" method, low performance
BI[] m = co[d];
string s = new string(d.ToString()[0], d); Write("{0}: ", d);
for (int i = 0, c = 0; c < ls; i++) {
if ((d * m[0]).ToString().Contains(s))
Write("{0} ", i, ++c);
for (int j = d, k = d - 1; j > 0; j = k--) m[k] += m[j];
}
fin();
}
static string scale(uint s, ref LI x) { // performs a small multiply and returns a string value
ulong Lo = x.lo * s, Ml = x.ml * s, Mh = x.mh * s, Hi = x.hi * s, Tp = x.tp * s;
while (Lo >= Lm) { Lo -= Lm; Ml++; }
while (Ml >= Lm) { Ml -= Lm; Mh++; }
while (Mh >= Lm) { Mh -= Lm; Hi++; }
while (Hi >= Lm) { Hi -= Lm; Tp++; }
if (Tp > 0) return Tp.ToString() + Hi.ToString(Fm) + Mh.ToString(Fm) + Ml.ToString(Fm) + Lo.ToString(Fm);
if (Hi > 0) return Hi.ToString() + Mh.ToString(Fm) + Ml.ToString(Fm) + Lo.ToString(Fm);
if (Mh > 0) return Mh.ToString() + Ml.ToString(Fm) + Lo.ToString(Fm);
if (Ml > 0) return Ml.ToString() + Lo.ToString(Fm);
return Lo.ToString();
}
static void funF(int d) { // structure of UInt64 method, high performance
LI[] m = Co[d];
string s = new string(d.ToString()[0], d); Write("{0}: ", d);
for (int i = d, c = 0; c < ls; i++) {
if (scale((uint)d, ref m[0]).Contains(s))
Write("{0} ", i, ++c);
for (int j = d, k = d - 1; j > 0; j = k--)
inc(ref m[k], m[j]);
}
fin();
}
static void init() { // initializes co and Co
for (int v = 1; v < 10; v++) {
BI[] res = new BI[v + 1];
long[] f = new long[v + 1], l = new long[v + 1];
for (int j = 0; j <= v; j++) {
if (j == v) {
LI[] t = new LI[v + 1];
for (int y = 0; y <= v; y++) set(ref t[y], (UInt64)f[y]);
Co.Add(t);
}
res[j] = f[j];
l[0] = f[0]; f[0] = ipow(j + 1, v);
for (int a = 0, b = 1; b <= v; a = b++) {
l[b] = f[b]; f[b] = f[a] - l[a];
}
}
for (int z = res.Length - 2; z > 0; z -= 2) res[z] *= -1;
co.Add(res);
}
}
static DateTime st;
static void doOne(string title, int top, Action<int> func) {
WriteLine('\n' + title); st = DateTime.Now;
for (int i = 2; i <= top; i++) func(i);
}
static void Main(string[] args)
{
init(); const int top = 9;
doOne("BigInteger mostly addition:", top, funS);
doOne("BigInteger.Pow():", top, funM);
doOne("UInt64 structure mostly addition:", top, funF);
}
}
- Output:
BigInteger mostly addition: 2: 19 31 69 81 105 106 107 119 127 131 0.007s 3: 261 462 471 481 558 753 1036 1046 1471 1645 0.008s 4: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 0.014s 5: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 0.033s 6: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 0.584s 7: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 2.891s 8: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 20.47s 9: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 226.7s BigInteger.Pow(): 2: 19 31 69 81 105 106 107 119 127 131 0.002s 3: 261 462 471 481 558 753 1036 1046 1471 1645 0.003s 4: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 0.008s 5: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 0.025s 6: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 0.450s 7: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 2.092s 8: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 14.80s 9: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 170.8s UInt64 structure mostly addition: 2: 19 31 69 81 105 106 107 119 127 131 0.004s 3: 261 462 471 481 558 753 1036 1046 1471 1645 0.004s 4: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 0.006s 5: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 0.013s 6: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 0.188s 7: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 1.153s 8: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 9.783s 9: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 121.3s
Results from a core i7-7700 @ 3.6Ghz. The UInt64 structure method is quicker, but it's likely because the BigInteger.ToString() implementation in C# is so sluggish. I've ported this (UInt64 structure) algorithm to C++, however it's quite a bit slower than the C++ GMP version.
Regarding the term "mostly addition", for this task there is some multiplication by a small integer (2 thru 9 in scale()), but the powers of "n" are calculated by only addition. The initial tables are calculated with multiplication and a power function (ipow()).
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>
int main() {
for (unsigned int d = 2; d <= 9; ++d) {
printf("First 10 super-%u numbers:\n", d);
char digits[16] = { 0 };
memset(digits, '0' + d, d);
mpz_t bignum;
mpz_init(bignum);
for (unsigned int count = 0, n = 1; count < 10; ++n) {
mpz_ui_pow_ui(bignum, n, d);
mpz_mul_ui(bignum, bignum, d);
char* str = mpz_get_str(NULL, 10, bignum);
if (strstr(str, digits)) {
printf("%u ", n);
++count;
}
free(str);
}
mpz_clear(bignum);
printf("\n");
}
return 0;
}
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 First 10 super-9 numbers: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181
C++
There are insufficiant bits avalaible to calculate the super-5 or super-6 numbers without a biginteger library
#include <iostream>
#include <sstream>
#include <vector>
uint64_t ipow(uint64_t base, uint64_t exp) {
uint64_t result = 1;
while (exp) {
if (exp & 1) {
result *= base;
}
exp >>= 1;
base *= base;
}
return result;
}
int main() {
using namespace std;
vector<string> rd{ "22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999" };
for (uint64_t ii = 2; ii < 5; ii++) {
cout << "First 10 super-" << ii << " numbers:\n";
int count = 0;
for (uint64_t j = 3; /* empty */; j++) {
auto k = ii * ipow(j, ii);
auto kstr = to_string(k);
auto needle = rd[(size_t)(ii - 2)];
auto res = kstr.find(needle);
if (res != string::npos) {
count++;
cout << j << ' ';
if (count == 10) {
cout << "\n\n";
break;
}
}
}
}
return 0;
}
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680
Alternative using GMP
#include <iostream>
#include <gmpxx.h>
using big_int = mpz_class;
int main() {
for (unsigned int d = 2; d <= 9; ++d) {
std::cout << "First 10 super-" << d << " numbers:\n";
std::string digits(d, '0' + d);
big_int bignum;
for (unsigned int count = 0, n = 1; count < 10; ++n) {
mpz_ui_pow_ui(bignum.get_mpz_t(), n, d);
bignum *= d;
auto str(bignum.get_str());
if (str.find(digits) != std::string::npos) {
std::cout << n << ' ';
++count;
}
}
std::cout << '\n';
}
return 0;
}
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 First 10 super-9 numbers: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181
Alternative not using GMP
#include <cstdio>
#include <sstream>
#include <chrono>
using namespace std;
using namespace chrono;
struct LI { uint64_t a, b, c, d, e; }; const uint64_t Lm = 1e18;
auto st = steady_clock::now(); LI k[10][10];
string padZ(uint64_t x, int n = 18) { string r = to_string(x);
return string(max((int)(n - r.length()), 0), '0') + r; }
uint64_t ipow(uint64_t b, uint64_t e) { uint64_t r = 1;
while (e) { if (e & 1) r *= b; e >>= 1; b *= b; } return r; }
uint64_t fa(uint64_t x) { // factorial
uint64_t r = 1; while (x > 1) r *= x--; return r; }
void set(LI &d, uint64_t s) { // d = s
d.a = s; d.b = d.c = d.d = d.e = 0; }
void inc(LI &d, LI s) { // d += s
d.a += s.a; while (d.a >= Lm) { d.a -= Lm; d.b++; }
d.b += s.b; while (d.b >= Lm) { d.b -= Lm; d.c++; }
d.c += s.c; while (d.c >= Lm) { d.c -= Lm; d.d++; }
d.d += s.d; while (d.d >= Lm) { d.d -= Lm; d.e++; }
d.e += s.e;
}
string scale(uint32_t s, LI &x) { // multiplies x by s, converts to string
uint64_t A = x.a * s, B = x.b * s, C = x.c * s, D = x.d * s, E = x.e * s;
while (A >= Lm) { A -= Lm; B++; }
while (B >= Lm) { B -= Lm; C++; }
while (C >= Lm) { C -= Lm; D++; }
while (D >= Lm) { D -= Lm; E++; }
if (E > 0) return to_string(E) + padZ(D) + padZ(C) + padZ(B) + padZ(A);
if (D > 0) return to_string(D) + padZ(C) + padZ(B) + padZ(A);
if (C > 0) return to_string(C) + padZ(B) + padZ(A);
if (B > 0) return to_string(B) + padZ(A);
return to_string(A);
}
void fun(int d) {
auto m = k[d]; string s = string(d, '0' + d); printf("%d: ", d);
for (int i = d, c = 0; c < 10; i++) {
if (scale((uint32_t)d, m[0]).find(s) != string::npos) {
printf("%d ", i); ++c; }
for (int j = d, k = d - 1; j > 0; j = k--) inc(m[k], m[j]);
} printf("%ss\n", to_string(duration<double>(steady_clock::now() - st).count()).substr(0,5).c_str());
}
static void init() {
for (int v = 1; v < 10; v++) {
uint64_t f[v + 1], l[v + 1];
for (int j = 0; j <= v; j++) {
if (j == v) for (int y = 0; y <= v; y++)
set(k[v][y], v != y ? (uint64_t)f[y] : fa(v));
l[0] = f[0]; f[0] = ipow(j + 1, v);
for (int a = 0, b = 1; b <= v; a = b++) {
l[b] = f[b]; f[b] = f[a] - l[a];
}
}
}
}
int main() {
init();
for (int i = 2; i <= 9; i++) fun(i);
}
- Output:
2: 19 31 69 81 105 106 107 119 127 131 0.002s 3: 261 462 471 481 558 753 1036 1046 1471 1645 0.004s 4: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 0.009s 5: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 0.026s 6: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 0.399s 7: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 2.523s 8: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 22.32s 9: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 275.4s
Slower than GMP on the core i7-7700 @ 3.6Ghz, over twice as slow. This one is 275 seconds, vs. 102 seconds for GMP.
Clojure
A more naïve implementation inspired by the Raku one, but without its use of parallelism; on my somewhat old and underpowered laptop, it gets through the basic task of 2 through 6 in about 6 seconds, then takes almost 40 to complete 7, and about six minutes for 8; with that growth rate, I didn't wait around for nine to complete.
(defn super [d]
(let [run (apply str (repeat d (str d)))]
(filter #(clojure.string/includes? (str (* d (Math/pow % d ))) run) (range))))
(doseq [d (range 2 9)]
(println (str d ": ") (take 10 (super d))))
- Output:
2: (19 31 69 81 105 106 107 119 127 131) 3: (261 462 471 558 753 1046 1471 1645 1752 1848) 4: (1168 4972 7423 7752 8431 11317 11487 11549 11680 16588) 5: (4602 5517 7539 9469 12955 14555 20137 20379 26629 35689) 6: (223763 302693 323576 513675 678146 1183741 1324944 1523993 1640026 1756271) 7: (4258476 9438581 10900183 11497728 12380285 12834193 13658671 14290071 16034108 16046124) 8: (29242698 43307276 44263715 45980752 54555936 81044125 126984952 133579963 142631696 152390251)
D
import std.bigint;
import std.conv;
import std.stdio;
import std.string;
void main() {
auto rd = ["22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999"];
BigInt one = 1;
BigInt nine = 9;
for (int ii = 2; ii <= 9; ii++) {
writefln("First 10 super-%d numbers:", ii);
auto count = 0;
inner:
for (BigInt j = 3; ; j++) {
auto k = ii * j ^^ ii;
auto ix = k.to!string.indexOf(rd[ii-2]);
if (ix >= 0) {
count++;
write(j, ' ');
if (count == 10) {
writeln();
writeln();
break inner;
}
}
}
}
}
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 First 10 super-9 numbers: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181
F#
- The Function
// Generate Super-N numbers. Nigel Galloway: October 12th., 2019
let superD N=
let I=bigint(pown 10 N)
let G=bigint N
let E=G*(111111111I%I)
let rec fL n=match (E-n%I).IsZero with true->true |_->if (E*10I)<n then false else fL (n/10I)
seq{1I..999999999999999999I}|>Seq.choose(fun n->if fL (G*n**N) then Some n else None)
- The Task
superD 2 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn ""
superD 3 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn ""
superD 4 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn ""
superD 5 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn ""
superD 6 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn ""
superD 7 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn ""
superD 8 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn ""
superD 9 |> Seq.take 10 |> Seq.iter(printf "%A "); printfn ""
- Output:
19 31 69 81 105 106 107 119 127 131 261 462 471 481 558 753 1036 1046 1471 1645 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181
Factor
USING: arrays formatting io kernel lists lists.lazy math
math.functions math.ranges math.text.utils prettyprint sequences
;
IN: rosetta-code.super-d
: super-d? ( seq n d -- ? ) tuck ^ * 1 digit-groups subseq? ;
: super-d ( d -- list )
[ dup <array> ] [ drop 1 lfrom ] [ ] tri [ super-d? ] curry
with lfilter ;
: super-d-demo ( -- )
10 2 6 [a,b] [
dup "First 10 super-%d numbers:\n" printf
super-d ltake list>array [ pprint bl ] each nl nl
] with each ;
MAIN: super-d-demo
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146
FreeBASIC
Dim rd(7) As String = {"22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999"}
For n As Integer = 2 To 9
Dim cont As Integer = 0
Dim j As Uinteger = 3
Print Using !"\nFirst 10 super-# numbers:"; n
Do
Dim k As Ulongint = n * (j ^ n)
Dim ix As Uinteger = Instr(Str(k), rd(n - 2))
If ix > 0 Then
cont += 1
Print j; " " ;
End If
j += 1
Loop Until cont = 10
Next n
Fōrmulæ
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in its website.
In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution
Case 1. Write a function/procedure/routine to find super-d numbers
Case 2. For d=2 through d=9, use the routine to show the first 1 ssuper-d numbers
Go
Simple brute force approach and so not particularly quick - about 2.25 minutes on a Core i7.
package main
import (
"fmt"
"math/big"
"strings"
"time"
)
func main() {
start := time.Now()
rd := []string{"22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999"}
one := big.NewInt(1)
nine := big.NewInt(9)
for i := big.NewInt(2); i.Cmp(nine) <= 0; i.Add(i, one) {
fmt.Printf("First 10 super-%d numbers:\n", i)
ii := i.Uint64()
k := new(big.Int)
count := 0
inner:
for j := big.NewInt(3); ; j.Add(j, one) {
k.Exp(j, i, nil)
k.Mul(i, k)
ix := strings.Index(k.String(), rd[ii-2])
if ix >= 0 {
count++
fmt.Printf("%d ", j)
if count == 10 {
fmt.Printf("\nfound in %d ms\n\n", time.Since(start).Milliseconds())
break inner
}
}
}
}
}
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 found in 0 ms First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 found in 1 ms First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 found in 7 ms First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 found in 28 ms First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 found in 285 ms First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 found in 1517 ms First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 found in 11117 ms First 10 super-9 numbers: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 found in 135616 ms
Haskell
import Data.List (isInfixOf)
import Data.Char (intToDigit)
isSuperd :: (Show a, Integral a) => a -> a -> Bool
isSuperd p n =
(replicate <*> intToDigit) (fromIntegral p) `isInfixOf` show (p * n ^ p)
findSuperd :: (Show a, Integral a) => a -> [a]
findSuperd p = filter (isSuperd p) [1 ..]
main :: IO ()
main =
mapM_
(putStrLn .
("First 10 super-" ++) .
((++) . show <*> ((" : " ++) . show . take 10 . findSuperd)))
[2 .. 6]
- Output:
First 10 super-2 : [19,31,69,81,105,106,107,119,127,131] First 10 super-3 : [261,462,471,481,558,753,1036,1046,1471,1645] First 10 super-4 : [1168,4972,7423,7752,8431,10267,11317,11487,11549,11680] First 10 super-5 : [4602,5517,7539,12955,14555,20137,20379,26629,32767,35689] First 10 super-6 : [27257,272570,302693,323576,364509,502785,513675,537771,676657,678146]
J
superD=: 1 e. #~@[ E. 10 #.inv ([ * ^~)&x: assert 3 superD 753 assert -. 2 superD 753 2 3 4 5 6 ,. _ 10 {. I. 2 3 4 5 6 superD&>/i.1e6 2 19 31 69 81 105 106 107 119 127 131 3 261 462 471 481 558 753 1036 1046 1471 1645 4 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 5 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 6 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146
Java
import java.math.BigInteger;
public class SuperDNumbers {
public static void main(String[] args) {
for ( int i = 2 ; i <= 9 ; i++ ) {
superD(i, 10);
}
}
private static final void superD(int d, int max) {
long start = System.currentTimeMillis();
String test = "";
for ( int i = 0 ; i < d ; i++ ) {
test += (""+d);
}
int n = 0;
int i = 0;
System.out.printf("First %d super-%d numbers: %n", max, d);
while ( n < max ) {
i++;
BigInteger val = BigInteger.valueOf(d).multiply(BigInteger.valueOf(i).pow(d));
if ( val.toString().contains(test) ) {
n++;
System.out.printf("%d ", i);
}
}
long end = System.currentTimeMillis();
System.out.printf("%nRun time %d ms%n%n", end-start);
}
}
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 Run time 6 ms First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 Run time 7 ms First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 Run time 13 ms First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 Run time 67 ms First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 Run time 546 ms First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 Run time 2342 ms First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 Run time 20545 ms First 10 super-9 numbers: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 Run time 268460 ms
jq
Works with gojq, the Go implementation of jq
The C implementation of jq does not have sufficiently accurate integer arithmetic to fulfill the task, so the output shown below is based on a run of gojq.
# To take advantage of gojq's arbitrary-precision integer arithmetic:
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
# Input is $d, the number of consecutive digits, 2 <= $d <= 9
# $max is the number of superd numbers to be emitted.
def superd($number):
. as $d
| tostring as $s
| ($s * $d) as $target
| {count:0, j: 3 }
| while ( .count <= $number;
.emit = null
| if ((.j|power($d) * $d) | tostring) | index($target)
then .count += 1
| .emit = .j
else .
end
| .j += 1 )
| select(.emit).emit ;
# super-d for 2 <=d < 8
range(2; 8)
| "First 10 super-\(.) numbers:",
superd(10)
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763
Julia
function superd(N)
println("First 10 super-$N numbers:")
count, j = 0, BigInt(3)
target = Char('0' + N)^N
while count < 10
if occursin(target, string(j^N * N))
count += 1
print("$j ")
end
j += 1
end
println()
end
for n in 2:9
@time superd(n)
end
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 0.017720 seconds (32.80 k allocations: 1.538 MiB) First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 0.003976 seconds (47.33 k allocations: 985.352 KiB) First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 0.018958 seconds (327.37 k allocations: 6.808 MiB) First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 0.060683 seconds (1.02 M allocations: 21.561 MiB) First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 1.395905 seconds (19.14 M allocations: 419.551 MiB, 19.77% gc time) First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 5.604611 seconds (77.81 M allocations: 1.687 GiB, 18.66% gc time) First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 38.827266 seconds (539.13 M allocations: 12.106 GiB, 19.11% gc time) First 10 super-9 numbers: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 380.576442 seconds (5.26 G allocations: 124.027 GiB, 18.02% gc time)
Kotlin
import java.math.BigInteger
fun superD(d: Int, max: Int) {
val start = System.currentTimeMillis()
var test = ""
for (i in 0 until d) {
test += d
}
var n = 0
var i = 0
println("First $max super-$d numbers:")
while (n < max) {
i++
val value: Any = BigInteger.valueOf(d.toLong()) * BigInteger.valueOf(i.toLong()).pow(d)
if (value.toString().contains(test)) {
n++
print("$i ")
}
}
val end = System.currentTimeMillis()
println("\nRun time ${end - start} ms\n")
}
fun main() {
for (i in 2..9) {
superD(i, 10)
}
}
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 Run time 31 ms First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 Run time 16 ms First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 Run time 25 ms First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 Run time 290 ms First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 Run time 1203 ms First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 Run time 3876 ms First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 Run time 29817 ms First 10 super-9 numbers: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 Run time 392181 ms
Lua
Lua - using doubles
Lua's default numeric type is IEEE-754 doubles, which are insufficient beyond d=5, but for reference:
for d = 2, 5 do
local n, found = 0, {}
local dds = string.rep(d, d)
while #found < 10 do
local dnd = string.format("%15.f", d * n ^ d)
if string.find(dnd, dds) then found[#found+1] = n end
n = n + 1
end
print("super-" .. d .. ": " .. table.concat(found,", "))
end
- Output:
super-2: 19, 31, 69, 81, 105, 106, 107, 119, 127, 131 super-3: 261, 462, 471, 481, 558, 753, 1036, 1046, 1471, 1645 super-4: 1168, 4972, 7423, 7752, 8431, 10267, 11317, 11487, 11549, 11680 super-5: 4602, 5517, 7539, 9469, 12955, 14555, 20137, 20379, 26629, 35689
Lua - using lbc
Using the lbc library to provide support for arbitrary-precision integers, which are sufficient for both task and extra-credit:
bc = require("bc")
for i = 2, 9 do
local d, n, found = bc.new(i), bc.new(0), {}
local dds = string.rep(d:tostring(), d:tonumber())
while #found < 10 do
local dnd = (d * n ^ d):tostring()
if string.find(dnd, dds) then found[#found+1] = n:tostring() end
n = n + 1
end
print("super-" .. d:tostring() .. ": " .. table.concat(found,", "))
end
- Output:
super-2: 19, 31, 69, 81, 105, 106, 107, 119, 127, 131 super-3: 261, 462, 471, 481, 558, 753, 1036, 1046, 1471, 1645 super-4: 1168, 4972, 7423, 7752, 8431, 10267, 11317, 11487, 11549, 11680 super-5: 4602, 5517, 7539, 12955, 14555, 20137, 20379, 26629, 32767, 35689 super-6: 27257, 272570, 302693, 323576, 364509, 502785, 513675, 537771, 676657, 678146 super-7: 140997, 490996, 1184321, 1259609, 1409970, 1783166, 1886654, 1977538, 2457756, 2714763 super-8: 185423, 641519, 1551728, 1854230, 6415190, 12043464, 12147605, 15517280, 16561735, 18542300 super-9: 17546133, 32613656, 93568867, 107225764, 109255734, 113315082, 121251742, 175461330, 180917907, 182557181
Mathematica / Wolfram Language
ClearAll[SuperD]
SuperD[d_, m_] := Module[{n, res, num},
res = {};
n = 1;
While[Length[res] < m,
num = IntegerDigits[d n^d];
If[MatchQ[num, {___, Repeated[d, {d}], ___}],
AppendTo[res, n]
];
n++;
];
res
]
Scan[Print[SuperD[#, 10]] &, Range[2, 6]]
- Output:
{19,31,69,81,105,106,107,119,127,131} {261,462,471,481,558,753,1036,1046,1471,1645} {1168,4972,7423,7752,8431,10267,11317,11487,11549,11680} {4602,5517,7539,12955,14555,20137,20379,26629,32767,35689} {27257,272570,302693,323576,364509,502785,513675,537771,676657,678146}
Nim
Using only the standard library, we would be limited to "d = 2, 3, 4". So, here is the program using the third-party library "bignum".
import sequtils, strutils, times
import bignum
iterator superDNumbers(d, maxCount: Positive): Natural =
var count = 0
var n = 2
let e = culong(d) # Bignum ^ requires a culong as exponent.
let pattern = repeat(chr(d + ord('0')), d)
while count != maxCount:
if pattern in $(d * n ^ e):
yield n
inc count
inc n, 1
let t0 = getTime()
for d in 2..9:
echo "First 10 super-$# numbers:".format(d)
echo toSeq(superDNumbers(d, 10)).join(" ")
echo "Time: ", getTime() - t0
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 First 10 super-9 numbers: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 Time: 1 minute, 43 seconds, 647 milliseconds, 920 microseconds, and 938 nanoseconds
Pascal
gmp is fast.Same brute force as Go
program Super_D;
uses
sysutils,gmp;
var
s :ansistring;
s_comp : ansistring;
test : mpz_t;
i,j,dgt,cnt : NativeUint;
Begin
mpz_init(test);
for dgt := 2 to 9 do
Begin
//create '22' to '999999999'
i := dgt;
For j := 2 to dgt do
i := i*10+dgt;
s_comp := IntToStr(i);
writeln('Finding ',s_comp,' in ',dgt,'*i**',dgt);
i := dgt;
cnt := 0;
repeat
mpz_ui_pow_ui(test,i,dgt);
mpz_mul_ui(test,test,dgt);
setlength(s,mpz_sizeinbase(test,10));
mpz_get_str(pChar(s),10,test);
IF Pos(s_comp,s) <> 0 then
Begin
write(i,' ');
inc(cnt);
end;
inc(i);
until cnt = 10;
writeln;
end;
mpz_clear(test);
End.
- Output:
Finding 22 in 2*i**2 19 31 69 81 105 106 107 119 127 131 Finding 333 in 3*i**3 261 462 471 481 558 753 1036 1046 1471 1645 Finding 4444 in 4*i**4 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 Finding 55555 in 5*i**5 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 Finding 666666 in 6*i**6 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 Finding 7777777 in 7*i**7 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 Finding 88888888 in 8*i**8 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 Finding 999999999 in 9*i**9 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 real 1m11,239s //only calc 9*i**9 [2..182557181] Finding 999999999 in 9*i**9 real 0m7,577s //calc 9*i**9 [2..182557181] and convert to String with preset length 100 -> takes longer to find '999999999' real 0m40,094s //calc 9*i**9 [2..182557181] and convert to String and setlength real 0m41,358s //complete task with finding Finding 999999999 in 9*i**9 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 real 1m5,134s
Perl
use strict;
use warnings;
use bigint;
use feature 'say';
sub super {
my $d = shift;
my $run = $d x $d;
my @super;
my $i = 0;
my $n = 0;
while ( $i < 10 ) {
if (index($n ** $d * $d, $run) > -1) {
push @super, $n;
++$i;
}
++$n;
}
@super;
}
say "\nFirst 10 super-$_ numbers:\n", join ' ', super($_) for 2..6;
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146
Phix
with javascript_semantics include mpfr.e procedure main() atom t0 = time() mpz k = mpz_init() for i=2 to iff(platform()=JS?7:9) do printf(1,"First 10 super-%d numbers:\n", i) integer count := 0, j = 3 string tgt = repeat('0'+i,i) while count<10 do mpz_ui_pow_ui(k,j,i) mpz_mul_si(k,k,i) string s = mpz_get_str(k) integer ix = match(tgt,s) if ix then count += 1 printf(1,"%d ", j) end if j += 1 end while printf(1,"\nfound in %s\n\n", {elapsed(time()-t0)}) end for end procedure main()
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 found in 0.0s First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 found in 0.0s First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 found in 0.2s First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 found in 0.5s First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 found in 6.8s First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 found in 33.2s First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 found in 3 minutes and 47s First 10 super-9 numbers: 17546133 <killed>
Since its actually about 3 times faster under pwa/p2js, I let that one run, just the once, keeping the above capped at 7 for ~11s:
... First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 found in 1 minute and 22s First 10 super-9 numbers: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 found in 16 minutes and 6s
Python
Procedural
from itertools import islice, count
def superd(d):
if d != int(d) or not 2 <= d <= 9:
raise ValueError("argument must be integer from 2 to 9 inclusive")
tofind = str(d) * d
for n in count(2):
if tofind in str(d * n ** d):
yield n
if __name__ == '__main__':
for d in range(2, 9):
print(f"{d}:", ', '.join(str(n) for n in islice(superd(d), 10)))
- Output:
2: 19, 31, 69, 81, 105, 106, 107, 119, 127, 131 3: 261, 462, 471, 481, 558, 753, 1036, 1046, 1471, 1645 4: 1168, 4972, 7423, 7752, 8431, 10267, 11317, 11487, 11549, 11680 5: 4602, 5517, 7539, 12955, 14555, 20137, 20379, 26629, 32767, 35689 6: 27257, 272570, 302693, 323576, 364509, 502785, 513675, 537771, 676657, 678146 7: 140997, 490996, 1184321, 1259609, 1409970, 1783166, 1886654, 1977538, 2457756, 2714763 8: 185423, 641519, 1551728, 1854230, 6415190, 12043464, 12147605, 15517280, 16561735, 18542300
Functional
'''Super-d numbers'''
from itertools import count, islice
from functools import reduce
# ------------------------ SUPER-D -------------------------
# super_d :: Int -> Either String [Int]
def super_d(d):
'''Either a message, if d is out of range, or
an infinite series of super_d numbers for d.
'''
if isinstance(d, int) and 1 < d < 10:
ds = d * str(d)
def p(x):
return ds in str(d * x ** d)
return Right(filter(p, count(2)))
else:
return Left(
'Super-d is defined only for integers drawn from {2..9}'
)
# ------------------------- TESTS --------------------------
# main :: IO ()
def main():
'''Attempted sampling of first 10 values for d <- [1..6],
where d = 1 is out of range.
'''
for v in map(
lambda x: either(
append(str(x) + ' :: ')
)(
compose(
append('First 10 super-' + str(x) + ': '),
showList
)
)(
bindLR(
super_d(x)
)(compose(Right, take(10)))
),
enumFromTo(1)(6)
): print(v)
# ------------------------ GENERIC -------------------------
# Left :: a -> Either a b
def Left(x):
'''Constructor for an empty Either (option type) value
with an associated string.
'''
return {'type': 'Either', 'Right': None, 'Left': x}
# Right :: b -> Either a b
def Right(x):
'''Constructor for a populated Either (option type) value'''
return {'type': 'Either', 'Left': None, 'Right': x}
# append (++) :: [a] -> [a] -> [a]
# append (++) :: String -> String -> String
def append(xs):
'''A list or string formed by
the concatenation of two others.
'''
def go(ys):
return xs + ys
return go
# bindLR (>>=) :: Either a -> (a -> Either b) -> Either b
def bindLR(m):
'''Either monad injection operator.
Two computations sequentially composed,
with any value produced by the first
passed as an argument to the second.
'''
def go(mf):
return (
mf(m.get('Right')) if None is m.get('Left') else m
)
return go
# compose :: ((a -> a), ...) -> (a -> a)
def compose(*fs):
'''Composition, from right to left,
of a series of functions.
'''
def go(f, g):
def fg(x):
return f(g(x))
return fg
return reduce(go, fs, lambda x: x)
# either :: (a -> c) -> (b -> c) -> Either a b -> c
def either(fl):
'''The application of fl to e if e is a Left value,
or the application of fr to e if e is a Right value.
'''
return lambda fr: lambda e: fl(e['Left']) if (
None is e['Right']
) else fr(e['Right'])
# enumFromTo :: Int -> Int -> [Int]
def enumFromTo(m):
'''Enumeration of integer values [m..n]
'''
return lambda n: range(m, 1 + n)
# showList :: [a] -> String
def showList(xs):
'''Stringification of a list.'''
return '[' + ','.join(str(x) for x in xs) + ']'
# take :: Int -> [a] -> [a]
# take :: Int -> String -> String
def take(n):
'''The prefix of xs of length n,
or xs itself if n > length xs.
'''
def go(xs):
return islice(xs, n)
return go
# MAIN ---
if __name__ == '__main__':
main()
- Output:
1 :: Super-d is defined only for integers drawn from {2..9} First 10 super-2: [19,31,69,81,105,106,107,119,127,131] First 10 super-3: [261,462,471,481,558,753,1036,1046,1471,1645] First 10 super-4: [1168,4972,7423,7752,8431,10267,11317,11487,11549,11680] First 10 super-5: [4602,5517,7539,12955,14555,20137,20379,26629,32767,35689] First 10 super-6: [27257,272570,302693,323576,364509,502785,513675,537771,676657,678146]
Quackery
from
, index
and end
are defined at Loops/Increment loop index within loop body#Quackery.
[ over findseq swap found ] is hasseq ( [ x --> b )
[ [] swap
[ 10 /mod
rot join swap
dup 0 = until ]
drop ] is digits ( n --> [ )
[ over ** over * digits
swap dup of hasseq ] is superd ( n --> b )
[] 5 times
[ [] 1 from
[ i^ 2 + index
superd if [ index join ]
dup size 10 = if end ]
nested join ]
witheach
[ i^ 2 + echo say " -> " echo cr ]
- Output:
2 -> [ 19 31 69 81 105 106 107 119 127 131 ] 3 -> [ 261 462 471 481 558 753 1036 1046 1471 1645 ] 4 -> [ 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 ] 5 -> [ 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 ] 6 -> [ 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 ]
R
Library is necessary to go beyond super-4 numbers. Indeed Rmpfr allows to augment precision for floating point numbers. I didn't go for extra task, because it took some minutes for super-6 numbers.
library(Rmpfr)
options(scipen = 999)
find_super_d_number <- function(d, N = 10){
super_number <- c(NA)
n = 0
n_found = 0
while(length(super_number) < N){
n = n + 1
test = d * mpfr(n, precBits = 200) ** d #Here I augment precision
test_formatted = .mpfr2str(test)$str #and I extract the string from S4 class object
iterable = strsplit(test_formatted, "")[[1]]
if (length(iterable) < d) next
for(i in d:length(iterable)){
if (iterable[i] != d) next
equalities = 0
for(j in 1:d) {
if (i == j) break
if(iterable[i] == iterable[i-j])
equalities = equalities + 1
else break
}
if (equalities >= (d-1)) {
n_found = n_found + 1
super_number[n_found] = n
break
}
}
}
message(paste0("First ", N, " super-", d, " numbers:"))
print((super_number))
return(super_number)
}
for(d in 2:6){find_super_d_number(d, N = 10)}
- Output:
First 10 super-2 numbers: [1] 19 31 69 81 105 106 107 119 127 131 First 10 super-3 numbers: [1] 261 462 471 481 558 753 1036 1046 1471 1645 First 10 super-4 numbers: [1] 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 First 10 super-5 numbers: [1] 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 First 10 super-6 numbers: [1] 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146
Raku
(formerly Perl 6)
2 - 6 take a few seconds, 7 about 17 seconds, 8 about 90... 9, bleh... around 700 seconds.
sub super (\d) {
my \run = d x d;
^∞ .hyper.grep: -> \n { (d * n ** d).Str.contains: run }
}
(2..9).race(:1batch).map: {
my $now = now;
put "\nFirst 10 super-$_ numbers:\n{.&super[^10]}\n{(now - $now).round(.1)} sec."
}
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 0.1 sec. First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 0.1 sec. First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 0.3 sec. First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 0.6 sec. First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 5.2 sec. First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 17.1 sec. First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 92.1 sec. First 10 super-9 numbers: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 704.7 sec.
REXX
/*REXX program computes and displays the first N super─d numbers for D from LO to HI.*/
numeric digits 100 /*ensure enough decimal digs for calc. */
parse arg n LO HI . /*obtain optional arguments from the CL*/
if n=='' | n=="," then n= 10 /*the number of super─d numbers to calc*/
if LO=='' | LO=="," then LO= 2 /*low end of D for the super─d nums.*/
if HI=='' | HI=="," then HI= 9 /*high " " " " " " " */
/* [↓] process D from LO ──► HI. */
do d=LO to HI; #= 0; $= /*count & list of super─d nums (so far)*/
z= copies(d, d) /*the string that is being searched for*/
do j=2 until #==n /*search for super─d numbers 'til found*/
if pos(z, d * j**d)==0 then iterate /*does product have the required reps? */
#= # + 1; $= $ j /*bump counter; add the number to list*/
end /*j*/
say
say center(' the first ' n " super-"d 'numbers ', digits(), "═")
say $
end /*d*/ /*stick a fork in it, we're all done. */
- output when using the default inputs:
══════════════════════════════════ the first 10 super-2 numbers ══════════════════════════════════ 19 31 69 81 105 106 107 119 127 131 ══════════════════════════════════ the first 10 super-3 numbers ══════════════════════════════════ 261 462 471 481 558 753 1036 1046 1471 1645 ══════════════════════════════════ the first 10 super-4 numbers ══════════════════════════════════ 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 ══════════════════════════════════ the first 10 super-5 numbers ══════════════════════════════════ 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 ══════════════════════════════════ the first 10 super-6 numbers ══════════════════════════════════ 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 ══════════════════════════════════ the first 10 super-7 numbers ══════════════════════════════════ 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 ══════════════════════════════════ the first 10 super-8 numbers ══════════════════════════════════ 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 ══════════════════════════════════ the first 10 super-9 numbers ══════════════════════════════════ 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181
Ruby
(2..8).each do |d|
rep = d.to_s * d
print "#{d}: "
puts (2..).lazy.select{|n| (d * n**d).to_s.include?(rep) }.first(10).join(", ")
end
- Output:
2: 19, 31, 69, 81, 105, 106, 107, 119, 127, 131 3: 261, 462, 471, 481, 558, 753, 1036, 1046, 1471, 1645 4: 1168, 4972, 7423, 7752, 8431, 10267, 11317, 11487, 11549, 11680 5: 4602, 5517, 7539, 12955, 14555, 20137, 20379, 26629, 32767, 35689 6: 27257, 272570, 302693, 323576, 364509, 502785, 513675, 537771, 676657, 678146 7: 140997, 490996, 1184321, 1259609, 1409970, 1783166, 1886654, 1977538, 2457756, 2714763 8: 185423, 641519, 1551728, 1854230, 6415190, 12043464, 12147605, 15517280, 16561735, 18542300
The first 10 super_9 numbers (not shown) take about 540 seconds.
Rust
// [dependencies]
// rug = "1.9"
fn print_super_d_numbers(d: u32, limit: u32) {
use rug::Assign;
use rug::Integer;
println!("First {} super-{} numbers:", limit, d);
let digits = d.to_string().repeat(d as usize);
let mut count = 0;
let mut n = 1;
let mut s = Integer::new();
while count < limit {
s.assign(Integer::u_pow_u(n, d));
s *= d;
if s.to_string().contains(&digits) {
print!("{} ", n);
count += 1;
}
n += 1;
}
println!();
}
fn main() {
for d in 2..=9 {
print_super_d_numbers(d, 10);
}
}
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 First 10 super-9 numbers: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181
Sidef
func super_d(d) {
var D = Str(d)*d
1..Inf -> lazy.grep {|n| Str(d * n**d).contains(D) }
}
for d in (2..8) {
say ("#{d}: ", super_d(d).first(10))
}
- Output:
2: [19, 31, 69, 81, 105, 106, 107, 119, 127, 131] 3: [261, 462, 471, 481, 558, 753, 1036, 1046, 1471, 1645] 4: [1168, 4972, 7423, 7752, 8431, 10267, 11317, 11487, 11549, 11680] 5: [4602, 5517, 7539, 12955, 14555, 20137, 20379, 26629, 32767, 35689] 6: [27257, 272570, 302693, 323576, 364509, 502785, 513675, 537771, 676657, 678146] 7: [140997, 490996, 1184321, 1259609, 1409970, 1783166, 1886654, 1977538, 2457756, 2714763] 8: [185423, 641519, 1551728, 1854230, 6415190, 12043464, 12147605, 15517280, 16561735, 18542300]
Swift
import BigInt
import Foundation
let rd = ["22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999"]
for d in 2...9 {
print("First 10 super-\(d) numbers:")
var count = 0
var n = BigInt(3)
var k = BigInt(0)
while true {
k = n.power(d)
k *= BigInt(d)
if let _ = String(k).range(of: rd[d - 2]) {
count += 1
print(n, terminator: " ")
fflush(stdout)
guard count < 10 else {
break
}
}
n += 1
}
print()
print()
}
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 First 10 super-9 numbers: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181
Visual Basic .NET
Imports System.Numerics
Module Module1
Sub Main()
Dim rd = {"22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999"}
Dim one As BigInteger = 1
Dim nine As BigInteger = 9
For ii = 2 To 9
Console.WriteLine("First 10 super-{0} numbers:", ii)
Dim count = 0
Dim j As BigInteger = 3
While True
Dim k = ii * BigInteger.Pow(j, ii)
Dim ix = k.ToString.IndexOf(rd(ii - 2))
If ix >= 0 Then
count += 1
Console.Write("{0} ", j)
If count = 10 Then
Console.WriteLine()
Console.WriteLine()
Exit While
End If
End If
j += 1
End While
Next
End Sub
End Module
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 First 10 super-9 numbers: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181
Wren
CLI (BigInt)
Managed to get up to 8 but too slow for 9.
import "./big" for BigInt
import "./fmt" for Fmt
var start = System.clock
var rd = ["22", "333", "4444", "55555", "666666", "7777777", "88888888"]
for (i in 2..8) {
Fmt.print("First 10 super-$d numbers:", i)
var count = 0
var j = BigInt.three
while (true) {
var k = j.pow(i) * i
var ix = k.toString.indexOf(rd[i-2])
if (ix >= 0) {
count = count + 1
Fmt.write("$i ", j)
if (count == 10) {
Fmt.print("\nfound in $f seconds\n", System.clock - start)
break
}
}
j = j.inc
}
}
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 found in 0.000500 seconds First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 found in 0.007636 seconds First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 found in 0.070462 seconds First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 found in 0.388554 seconds First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 found in 10.044345 seconds First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 found in 62.021899 seconds First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 found in 434.536825 seconds
Embedded (GMP)
Much sprightlier with 8 now being reached in 11.7 seconds and 9 in 126.5 seconds.
/* Super-d_numbers_2.wren */
import "./gmp" for Mpz
import "./fmt" for Fmt
var start = System.clock
var rd = ["22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999"]
for (i in 2..9) {
Fmt.print("First 10 super-$d numbers:", i)
var count = 0
var j = Mpz.three
var k = Mpz.new()
while (true) {
k.pow(j, i).mul(i)
var ix = k.toString.indexOf(rd[i-2])
if (ix >= 0) {
count = count + 1
Fmt.write("$i ", j)
if (count == 10) {
Fmt.print("\nfound in $f seconds\n", System.clock - start)
break
}
}
j.inc
}
}
- Output:
First 10 super-2 numbers: 19 31 69 81 105 106 107 119 127 131 found in 0.000222 seconds First 10 super-3 numbers: 261 462 471 481 558 753 1036 1046 1471 1645 found in 0.001222 seconds First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 found in 0.007386 seconds First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 found in 0.024863 seconds First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 found in 0.339837 seconds First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 found in 1.684412 seconds First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 found in 11.695570 seconds First 10 super-9 numbers: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 found in 126.454911 seconds
zkl
GNU Multiple Precision Arithmetic Library
var [const] BI=Import("zklBigNum"); // libGMP
fcn superDW(d){
digits:=d.toString()*d;
[2..].tweak('wrap(n)
{ BI(n).pow(d).mul(d).toString().holds(digits) and n or Void.Skip });
}
foreach d in ([2..8]){ println(d," : ",superDW(d).walk(10).concat(" ")) }
- Output:
2 : 19 31 69 81 105 106 107 119 127 131 3 : 261 462 471 481 558 753 1036 1046 1471 1645 4 : 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 5 : 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 6 : 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 7 : 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 8 : 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300
- Programming Tasks
- Solutions by Programming Task
- 11l
- Amazing Hopper
- C sharp
- System.Numerics
- C
- GMP
- C++
- Clojure
- D
- F Sharp
- Factor
- FreeBASIC
- Fōrmulæ
- Go
- Haskell
- J
- Java
- Jq
- Julia
- Kotlin
- Lua
- Lua - using doubles
- Lua - using lbc
- Mathematica
- Wolfram Language
- Nim
- Bignum
- Pascal
- Perl
- Phix
- Python
- Quackery
- R
- Rmpfr
- Raku
- REXX
- Ruby
- Rust
- Sidef
- Swift
- AttaSwift BigInt
- Visual Basic .NET
- Wren
- Wren-big
- Wren-fmt
- Wren-gmp
- Zkl