Palindromic gapful numbers: Difference between revisions
Simplify the task description
(Simplify the task description) |
|||
| (6 intermediate revisions by 5 users not shown) | |||
Line 2:
{{task}}
For this task, a ''number'' is to be understood as a positive integer expressed in base ten,
and a ''palindromic'' number is one that is equal to the integer formed by reversing its decimal digits.
A number that is evenly divisible by the number formed by concatenating its
first and last digits in that order is known as a '''gapful number'''.
All one─ and two─digit numbers have this property and accordingly only
numbers greater than or equal to '''100''' should be considered for this Rosetta Code task.
(''Evenly divisible''
;Example:
Line 17 ⟶ 16:
number <big>'''17'''</big> which is formed by the first and last decimal digits
of <big> '''<u>1</u>03<u>7</u>'''. </big>
;Task:
Line 1,304 ⟶ 1,298:
8 : [808696968869696808]
9 : [968787783387787869]</pre>
===Translation of F#===
{{trans|Ruby of F#}}
<BR>Recursive version; max memory consumption hits ~22%; comment out necessary outputs to run.
<BR>May produce: "GC Warning: Repeated allocation of very large block (appr. size xxxxxx):" messages in output.
<BR>For Crystal >= 0.34, the operations &+, &*, and &** turnoff default compiler overflow checks.
System: I7-6700HQ, 3.5GHz, 16GB, Linux Kernel 5.9.10, Crystal 0.35.1
Run as: $ crystal run --release fsharp2crystal.cr
Best Time: 29.455717914 secs
<syntaxhighlight lang="ruby">class PalNo
@digit : UInt64
@dd : UInt64
def initialize(digit : Int32)
@digit, @l, @dd = digit.to_u64, 3, 11u64 * digit
end
def fN(n : Int32)
return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] of UInt64 if n == 1
return [0, 11, 22, 33, 44, 55, 66, 77, 88, 99] of UInt64 if n == 2
a = [] of UInt64
([0, 1, 2, 3, 4, 5, 6, 7, 8, 9] of UInt64).product(fN(n - 2)) do |g0, g1|
a << g0.to_u64 &* 10u64 &** (n - 1) &+ g0.to_u64 &+ 10u64 &* g1.to_u64
end
return a
end
def show(count, keep)
to_skip, palcnt, pals = count - keep, 0, [] of UInt64
while palcnt < count
fN(@l - 2).each do |g|
pal = @digit * 10u64 &** (@l - 1) + @digit + 10u64 &* g
pals << pal if pal % @dd == 0 && (palcnt += 1) > to_skip
break if palcnt - to_skip == keep
end
@l += 1
end
print pals; puts
end
end
start = Time.monotonic
(1..9).each { |digit| PalNo.new(digit).show(20, 20) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(100, 15) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(1000, 10) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(100_000, 1) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(1_000_000, 1) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(10_000_000, 1) }; puts "####"
puts (Time.monotonic - start).total_seconds
</syntaxhighlight>
{{out}}
<pre>
[121, 1001, 1111, 1221, 1331, 1441, 1551, 1661, 1771, 1881, 1991, 10901, 11011, 12221, 13431, 14641, 15851, 17171, 18381, 19591]
[242, 2002, 2112, 2222, 2332, 2442, 2552, 2662, 2772, 2882, 2992, 20702, 21912, 22022, 23232, 24442, 25652, 26862, 28182, 29392]
[363, 3003, 3333, 3663, 3993, 31713, 33033, 36663, 300003, 303303, 306603, 309903, 312213, 315513, 318813, 321123, 324423, 327723, 330033, 333333]
[484, 4004, 4224, 4444, 4664, 4884, 40304, 42724, 44044, 46464, 48884, 400004, 401104, 402204, 403304, 404404, 405504, 406604, 407704, 408804]
[5005, 5115, 5225, 5335, 5445, 5555, 5665, 5775, 5885, 5995, 50105, 51315, 52525, 53735, 54945, 55055, 56265, 57475, 58685, 59895]
[6006, 6336, 6666, 6996, 61116, 64746, 66066, 69696, 600006, 603306, 606606, 609906, 612216, 615516, 618816, 621126, 624426, 627726, 630036, 633336]
[7007, 7777, 77077, 700007, 707707, 710017, 717717, 720027, 727727, 730037, 737737, 740047, 747747, 750057, 757757, 760067, 767767, 770077, 777777, 780087]
[8008, 8448, 8888, 80608, 86768, 88088, 800008, 802208, 804408, 806608, 808808, 821128, 823328, 825528, 827728, 829928, 840048, 842248, 844448, 846648]
[9009, 9999, 94149, 99099, 900009, 909909, 918819, 927729, 936639, 945549, 954459, 963369, 972279, 981189, 990099, 999999, 9459549, 9508059, 9557559, 9606069]
####
[165561, 166661, 167761, 168861, 169961, 170071, 171171, 172271, 173371, 174471, 175571, 176671, 177771, 178871, 179971]
[265562, 266662, 267762, 268862, 269962, 270072, 271172, 272272, 273372, 274472, 275572, 276672, 277772, 278872, 279972]
[30366303, 30399303, 30422403, 30455403, 30488403, 30511503, 30544503, 30577503, 30600603, 30633603, 30666603, 30699603, 30722703, 30755703, 30788703]
[4473744, 4485844, 4497944, 4607064, 4619164, 4620264, 4632364, 4644464, 4656564, 4668664, 4681864, 4693964, 4803084, 4815184, 4827284]
[565565, 566665, 567765, 568865, 569965, 570075, 571175, 572275, 573375, 574475, 575575, 576675, 577775, 578875, 579975]
[60399306, 60422406, 60455406, 60488406, 60511506, 60544506, 60577506, 60600606, 60633606, 60666606, 60699606, 60722706, 60755706, 60788706, 60811806]
[72299227, 72322327, 72399327, 72422427, 72499427, 72522527, 72599527, 72622627, 72699627, 72722727, 72799727, 72822827, 72899827, 72922927, 72999927]
[80611608, 80622608, 80633608, 80644608, 80655608, 80666608, 80677608, 80688608, 80699608, 80800808, 80811808, 80822808, 80833808, 80844808, 80855808]
[95311359, 95400459, 95499459, 95588559, 95677659, 95766759, 95855859, 95944959, 96033069, 96122169, 96211269, 96300369, 96399369, 96488469, 96577569]
####
[17799771, 17800871, 17811871, 17822871, 17833871, 17844871, 17855871, 17866871, 17877871, 17888871]
[27799772, 27800872, 27811872, 27822872, 27833872, 27844872, 27855872, 27866872, 27877872, 27888872]
[3084004803, 3084334803, 3084664803, 3084994803, 3085225803, 3085555803, 3085885803, 3086116803, 3086446803, 3086776803]
[482282284, 482414284, 482535284, 482656284, 482777284, 482898284, 482909284, 483020384, 483141384, 483262384]
[57800875, 57811875, 57822875, 57833875, 57844875, 57855875, 57866875, 57877875, 57888875, 57899875]
[6084004806, 6084334806, 6084664806, 6084994806, 6085225806, 6085555806, 6085885806, 6086116806, 6086446806, 6086776806]
[7452992547, 7453223547, 7453993547, 7454224547, 7454994547, 7455225547, 7455995547, 7456226547, 7456996547, 7457227547]
[8085995808, 8086006808, 8086116808, 8086226808, 8086336808, 8086446808, 8086556808, 8086666808, 8086776808, 8086886808]
[9675005769, 9675995769, 9676886769, 9677777769, 9678668769, 9679559769, 9680440869, 9681331869, 9682222869, 9683113869]
####
[178788887871]
[278788887872]
[30878611687803]
[4833326233384]
[578789987875]
[60878611687806]
[74826144162847]
[80869688696808]
[96878077087869]
####
[17878799787871]
[27878799787872]
[3087876666787803]
[483333272333384]
[57878799787875]
[6087876996787806]
[7487226666227847]
[8086969559696808]
[9687870990787869]
####
[1787878888787871]
[2787878888787872]
[308787855558787803]
[48333332623333384]
[5787878998787875]
[608787855558787806]
[748867523325768847]
[808696968869696808]
[968787783387787869]
####
</pre>
=={{header|Delphi}}==
Line 1,313 ⟶ 1,422:
{-------------Library Routines ----------------------------------------------------------------}
procedure GetDigits(N: integer; var IA: TIntegerDynArray);
{Get an array of the integers in a number}
{Numbers returned from least to most significant}
var T,I,DC: integer;
begin
DC:=Trunc(Log10(N))+1;
SetLength(IA,DC);
for I:=0 to DC-1 do
begin
T:=N mod 10;
N:=N div 10;
IA[I]:=T;
end;
end;
function GetNKPalindrome(N,K: int64): int64;
Line 1,675 ⟶ 1,797:
Elapsed Time: 763.788 ms.
</pre>
Line 2,583 ⟶ 2,588:
8 : [8085995808, 8086006808, 8086116808, 8086226808, 8086336808, 8086446808, 8086556808, 8086666808, 8086776808, 8086886808]
9 : [9675005769, 9675995769, 9676886769, 9677777769, 9678668769, 9679559769, 9680440869, 9681331869, 9682222869, 9683113869]
</pre>
=={{header|jq}}==
'''Adapted from [[#Crystal|Crystal]]''' ("Direct Generation of Numbers")
'''Works with jq, the C implementation of jq'''
'''Works with gojq, the Go implementation of jq'''
The task as defined here (see "def task:") highlights the
relative strengths and weakness of the C and Go implementations of jq.
In general, jq supports the efficient processing of
streams, and the program presented below is accordingly based on a function
that generates a stream of the numbers of interest.
The C implementation of jq is careful about memory management and has
no problem completing the task. However this implementation relies
on IEEE 754 arithmetic and thus the accuracy of results for integers
with more than 15 digits cannot be relied on, and indeed the last line
in the transcript is erroneous, as indicated by the annotation.
The Go implementation of jq, by contrast, though offering support for
unbounded-precision integer arithmetic, is not so careful about memory
management, and the program exhausts memory fairly quickly, as also
indicated in the annotated transcript below.
<syntaxhighlight lang="jq">
### Generic functions
def power($a;$b): reduce range(0;$b) as $i (1; . * $a);
# Emit the reverse of the string $s
def reverse($s):
$s | tostring | split("") | reverse | join("");
def skip($n; stream):
foreach stream as $s (-1;
if . == $n then . else .+1 end;
select(. == $n) | $s);
### Palindromic gapful numbers
# Output: a stream of non-trivial palindromic gapful numbers ending in the specified digit
def palindromicgapfuls($digit):
{emit: null,
dd: (11 * $digit), # digit gapful divisor: 11, 22,...88, 99
power: 1}
| foreach range(0; infinite) as $_ (.;
.power += 1
| (power(10; .power / 2 | floor)) as $base # value of middle digit position: 10..
| ($base * 11) as $base11 # value of middle two digits positions: 110..
| ($base * $digit) as $this_lo # starting half for this digit: 10.. to 90..
| ($base * ($digit + 1)) as $next_lo # starting half for next digit: 20.. to 100..
| foreach range($this_lo; $next_lo; 10) as $front_half (.; # d_00; d_10; d_20; ...
($front_half|tostring) as $left_half
| reverse($left_half) as $right_half
| if .power%2 == 1
then .palindrome = (($left_half + $right_half) | tonumber)
| foreach range(0;10) as $i (.;
.emit = if .palindrome % .dd == 0
then .palindrome
else null
end
| .palindrome += $base11 )
else .palindrome = ((($left_half[:-1]) + $right_half) | tonumber)
| foreach range(0;10) as $i (.;
.emit = if .palindrome % .dd == 0
then .palindrome
else null
end
| .palindrome += $base )
end ) )
| select(.emit).emit ;
def palindromicgapfuls($count; $keep):
range(1; 10) as $digit
| "\($digit) : \([limit($keep; skip($count - $keep; palindromicgapfuls($digit)))])" ;
def task:
"First 20 non-trivial palindromic gapful numbers ending with:",
palindromicgapfuls(20; 20),
"\nLast 15 of first 100 non-trivial palindromic gapful numbers ending in:",
palindromicgapfuls(100; 15),
"\nLast 10 of first 1000 non-trivial palindromic gapful numbers ending in:",
palindromicgapfuls(1000; 10),
"\n100,000th non-trivial palindromic gapful number ending with:",
palindromicgapfuls(100000; 1),
"\n1,000,000th non-trivial palindromic gapful number ending with:",
palindromicgapfuls(1000000; 1);
task
</syntaxhighlight>
{{output}}
The output has been annotated, as explained above.
<pre>
First 20 non-trivial palindromic gapful numbers ending with:
1 : [121,1001,1111,1221,1331,1441,1551,1661,1771,1881,1991,10901,11011,12221,13431,14641,15851,17171,18381,19591]
2 : [242,2002,2112,2222,2332,2442,2552,2662,2772,2882,2992,20702,21912,22022,23232,24442,25652,26862,28182,29392]
3 : [363,3003,3333,3663,3993,31713,33033,36663,300003,303303,306603,309903,312213,315513,318813,321123,324423,327723,330033,333333]
4 : [484,4004,4224,4444,4664,4884,40304,42724,44044,46464,48884,400004,401104,402204,403304,404404,405504,406604,407704,408804]
5 : [5005,5115,5225,5335,5445,5555,5665,5775,5885,5995,50105,51315,52525,53735,54945,55055,56265,57475,58685,59895]
6 : [6006,6336,6666,6996,61116,64746,66066,69696,600006,603306,606606,609906,612216,615516,618816,621126,624426,627726,630036,633336]
7 : [7007,7777,77077,700007,707707,710017,717717,720027,727727,730037,737737,740047,747747,750057,757757,760067,767767,770077,777777,780087]
8 : [8008,8448,8888,80608,86768,88088,800008,802208,804408,806608,808808,821128,823328,825528,827728,829928,840048,842248,844448,846648]
9 : [9009,9999,94149,99099,900009,909909,918819,927729,936639,945549,954459,963369,972279,981189,990099,999999,9459549,9508059,9557559,9606069]
Last 15 of first 100 non-trivial palindromic gapful numbers ending in:
1 : [165561,166661,167761,168861,169961,170071,171171,172271,173371,174471,175571,176671,177771,178871,179971]
2 : [265562,266662,267762,268862,269962,270072,271172,272272,273372,274472,275572,276672,277772,278872,279972]
3 : [30366303,30399303,30422403,30455403,30488403,30511503,30544503,30577503,30600603,30633603,30666603,30699603,30722703,30755703,30788703]
4 : [4473744,4485844,4497944,4607064,4619164,4620264,4632364,4644464,4656564,4668664,4681864,4693964,4803084,4815184,4827284]
5 : [565565,566665,567765,568865,569965,570075,571175,572275,573375,574475,575575,576675,577775,578875,579975]
6 : [60399306,60422406,60455406,60488406,60511506,60544506,60577506,60600606,60633606,60666606,60699606,60722706,60755706,60788706,60811806]
7 : [72299227,72322327,72399327,72422427,72499427,72522527,72599527,72622627,72699627,72722727,72799727,72822827,72899827,72922927,72999927]
8 : [80611608,80622608,80633608,80644608,80655608,80666608,80677608,80688608,80699608,80800808,80811808,80822808,80833808,80844808,80855808]
9 : [95311359,95400459,95499459,95588559,95677659,95766759,95855859,95944959,96033069,96122169,96211269,96300369,96399369,96488469,96577569]
Last 10 of first 1000 non-trivial palindromic gapful numbers ending in:
1 : [17799771,17800871,17811871,17822871,17833871,17844871,17855871,17866871,17877871,17888871]
2 : [27799772,27800872,27811872,27822872,27833872,27844872,27855872,27866872,27877872,27888872]
3 : [3084004803,3084334803,3084664803,3084994803,3085225803,3085555803,3085885803,3086116803,3086446803,3086776803]
4 : [482282284,482414284,482535284,482656284,482777284,482898284,482909284,483020384,483141384,483262384]
5 : [57800875,57811875,57822875,57833875,57844875,57855875,57866875,57877875,57888875,57899875]
6 : [6084004806,6084334806,6084664806,6084994806,6085225806,6085555806,6085885806,6086116806,6086446806,6086776806]
7 : [7452992547,7453223547,7453993547,7454224547,7454994547,7455225547,7455995547,7456226547,7456996547,7457227547]
8 : [8085995808,8086006808,8086116808,8086226808,8086336808,8086446808,8086556808,8086666808,8086776808,8086886808]
9 : [9675005769,9675995769,9676886769,9677777769,9678668769,9679559769,9680440869,9681331869,9682222869,9683113869]
100,000th non-trivial palindromic gapful number ending with:
1 : [178788887871]
2 : [278788887872]
3 : [30878611687803]
4 : [4833326233384]
5 : [578789987875]
6 : [60878611687806]
7 : [74826144162847]
8 : [80869688696808]
9 : [96878077087869]
1,000,000th palindromic gapful number ending with:
1 : [17878799787871]
2 : [27878799787872]
3 : [3087876666787803]
4 : [483333272333384]
5 : [57878799787875]
6 : [6087876996787806]
#### gojq program terminated ####
7 : [7487226666227847]
8 : [8086969559696808]
9 : [97487364246378480] #### wrong
</pre>
Line 3,444 ⟶ 3,603:
=== Ludicrously fast to 10,000,000,000,000,000,000th ===
{{libheader|Phix/online}}
You can run this online [http://phix.x10.mx/p2js/pgn.htm here].
<!--<syntaxhighlight lang="phix">(phixonline)-->
Line 3,582 ⟶ 3,742:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">pals</span><span style="color: #0000FF;">,</span><span style="color: #000000;">palcount</span><span style="color: #0000FF;">,</span><span style="color: #000000;">skipn</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">palindromicgapfuls</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pals</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">skip</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">skipn</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Line 3,634 ⟶ 3,794:
<!--</syntaxhighlight>-->
{{out}}
<pre style="font-size:
First 20 palindromic gapful numbers ending with:
1: 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591
Line 5,349 ⟶ 5,509:
{{libheader|Wren-fmt}}
Search limited to the first 100,000 palindromic gapful numbers as, beyond that, the numbers become too large (>= 2 ^ 53) to be accurately represented by Wren's Num type.
<syntaxhighlight lang="
var reverse = Fn.new { |s|
| |||