Super-d numbers
Super-d numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
A super-d number is a positive integer n such that d × n^d has at least d consecutive digits d where
2 ≤ d ≤ 9
For instance, 753 is a super-3 number because 3 × 753^3 = 1280873331.
- 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)
- See also
Factor
<lang 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</lang>
- 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
Go
Simple brute force approach and so not particularly quick - about 2.5 minutes on a Core 17. <lang go>package main
import (
"fmt" "math/big" "strings" "time"
)
func pow(n uint64, exp int) *big.Int {
b := new(big.Int).SetUint64(n)
p := new(big.Int).Set(b)
for i := 2; i <= exp; i++ {
p.Mul(p, b)
}
return p
}
func main() {
start := time.Now()
rd := []string{"22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999"}
for i := 2; i <= 9; i++ {
fmt.Printf("First 10 super-%d numbers:\n", i)
bigi := big.NewInt(int64(i))
k := new(big.Int)
count := 0
inner:
for j := uint64(3); ; j++ {
k.Mul(bigi, pow(j, i))
ix := strings.Index(k.String(), rd[i-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
}
}
}
}
}</lang>
- 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 0 ms First 10 super-4 numbers: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 found in 5 ms First 10 super-5 numbers: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 found in 23 ms First 10 super-6 numbers: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 found in 350 ms First 10 super-7 numbers: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 found in 1768 ms First 10 super-8 numbers: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 found in 12912 ms First 10 super-9 numbers: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 found in 151070 ms
Perl 6
via map + grep:k + .index
2 - 6 takes a few seconds, 7 & 8 take a few minutes; I got tired of waiting for 9.
<lang perl6>my \n = 10;
sub super ($d) {
my $run = $d x $d;
"First {n} super-{$d} numbers:\n{ (^Inf .map( 0 ~ $d * * ** $d ).grep: *.index($run), :k)[^n] }\n"
}
- Required
.say for (2..6).map: -> $d { super $d }
- Optional
.say for (7..8).map: -> $d { super $d }</lang>
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
via grep + .contains in lazy array
<lang perl6> for 2..6 -> $d {
my $digits = $d x $d;
my @super = grep { ($_ ** $d * $d).contains($digits) }, ^Inf;
say "$d: ", @super.head(10);
} </lang>
- 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)