Super-d numbers
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.
#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
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_gmp.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
- 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