Palindromic gapful numbers: Difference between revisions

=={{header|AppleScript}}==

 

set part1 to {"First 20 palindromic gapful numbers > 100 ending with each digit from 1 to 9:"}

set part2 to {"86th to 100th such:"}

set AppleScript's text item delimiters to " "

repeat with endDigit from 1 to 9

set hi to baseHi

if (oddDigitCount) then

set temp to hi div 10

else

set temp to hi

end if

repeat until (temp is 0)

set temp to temp div 10

end repeat

set oddDigitCount to (not oddDigitCount)

set hi to baseHi

end if

end repeat

end repeat

set AppleScript's text item delimiters to linefeed

end doTask

 

 

{{output}}

17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871

27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872

482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384

57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875

 

=={{header|C}}==

{{trans|C++}}

#include <stdio.h>

#include <stdint.h>

 

return 0;

 

{{out}}

=={{header|C++}}==

The idea of generating palindromes first then testing for gapfulness was borrowed from other solutions.

#include <cstdint>

 

 

return 0;

 

{{out}}

=={{header|Crystal}}==

===Brute force and slow===

r1 = (10_u64**pow + 1) * digit

r2 = 10_u64**pow * (digit + 1)

count = 1000

puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:"

 

===Orders of Magnitude Faster: Direct Generation of Numbers===

Crystal is a statically typed and a compiled language.

<BR>The code as implemented has been tested to produce optimum performance.

Run as: $ crystal run --release palindromicgapfuls.cr

 

gapfuls = [] of UInt64 # array of palindromic gapfuls

(2..).select do |power|

base = 10_u64**(power >> 1) # value of middle digit position: 10..

next_lo = base * (digit + 1) # starting half for next digit: 20.. to 100..

this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_00; d_10; d_20; ...

if power.odd?

palindrome = (left_half + right_half).to_u64

10.times do

return gapfuls if gapfuls.size == count

palindrome += base11

palindrome = (left_half.rchop + right_half).to_u64

10.times do

return gapfuls if gapfuls.size == count

palindrome += base

1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }

 

 

Compact version: 22.0 secs

gapfuls = [] of UInt64 # array of palindromic gapfuls

(2..).select do |power|

base = 10_u64**(power >> 1) # value of middle digit position: 10..

palindrome = (left_half + right_half).to_u64

10.times do

return gapfuls if gapfuls.size == count

palindrome += basep

1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }

 

 

Object Oriented implementation: same speed - 21.8 seconds

<Br>Here using a Struct (allocated on stack) is faster than using a Class (allocated on heap)

include Enumerable(UInt64)

 

 

def initialize(@digit : Int32)

end

 

palindrome = (left_half + right_half).to_u64

10.times do

palindrome += base11

end

palindrome = (left_half.rchop + right_half).to_u64

10.times do

palindrome += base

end

1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }

 

 

Original version optimized for minimal memory use: 24.6 secs

palcnt = 0 # count of gapful palindromes

to_skip = count - keep # count of unwanted values to skip

gapfuls = [] of UInt64 # array of palindromic gapfuls

(2..).select do |power|

base = 10_u64**(power >> 1) # value of middle digit position: 10..

next_lo = base * (digit + 1) # starting half for next digit: 20.. to 100..

this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_00; d_10; d_20; ...

if power.odd?

palindrome = (left_half + right_half).to_u64

10.times do

palindrome += base11

end

palindrome = (left_half.rchop + right_half).to_u64

10.times do

palindrome += base

end

1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

 

 

Compact version optimized for minimal memory use: 24.5 secs

palcnt = 0 # count of gapful palindromes

to_skip = count - keep # count of unwanted values to skip

gapfuls = [] of UInt64 # array of palindromic gapfuls

(2..).select do |power|

base *= 10 if power.even? # value of middle digit position: 10..

palindrome = (left_half + right_half).to_u64

10.times do

palindrome += basep

end

end

end

1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

 

 

OOP version optimized for minimal memory use - 25.4 secs

<BR>It creates an output method that skips the unwanted values and only keeps/stores the desired ones.

include Enumerable(UInt64)

 

 

def initialize(@digit : Int32)

end

 

next_lo = base * (@digit + 1) # starting half for next digit: 20.. to 100..

this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_00; d_10; d_20; ...

if power.odd?

palindrome = (left_half + right_half).to_u64

10.times do

palindrome += base11

end

palindrome = (left_half.rchop + right_half).to_u64

10.times do

palindrome += base

end

1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }

 

 

Compact minimized memory version that numerically create palindromes: 9.2 secs

palcnt = 0 # count of gapful palindromes

to_skip = count - keep # count of unwanted values to skip

gapfuls = [] of UInt64 # array of palindromic gapfuls

(2..).select do |power|

base *= 10 if power.even? # value of middle digit position: 10..

palindrome = make_palindrome(front_half, power)

10.times do

palindrome += basep

end

end

end

result //= 10 if power.even?

while front_half > 0

front_half //= 10

end

1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

 

 

OOP version optimized for minimal memory use, palindromes created numerically - 9.59 secs

include Enumerable(UInt64)

def initialize(@digit : Int32)

end

palindrome = make_palindrome(front_half, power)

10.times do

palindrome += basep

end

end

 

# Optimized output method: only keep desired values.

def keep_from(count, keep)

return kept if kept.size == keep

end

end

end

start = Time.monotonic

count, keep = 20, 20

puts "First 20 palindromic gapful numbers ending with:"

1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }

count, keep = 100, 15

puts "\nLast 15 of first 100 palindromic gapful numbers ending in:"

1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }

count, keep = 1_000, 10

puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:"

1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }

count, keep = 100_000, 1

puts "\n100,000th palindromic gapful number ending with:"

1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }

count, keep = 1_000_000, 1

puts "\n1,000,000th palindromic gapful number ending with:"

1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }

count, keep = 10_000_000, 1

puts "\n10,000,000th palindromic gapful number ending with:"

1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }

 

{{out}}

Run as: $ crystal run --release fsharp2crystal.cr

Best Time: 29.455717914 secs

@digit : UInt64

@dd : UInt64

 

puts (Time.monotonic - start).total_seconds

{{out}}

<pre>

[968787783387787869]

####

</pre>

 

=={{header|F_Sharp|F#}}==

// Palindromic Gapful Numbers . Nigel Galloway: December 3rd., 2020

let rec fN g l=seq{match l with 3->yield! seq{for n in 0L..9L->g*100L+g+n*10L}

[1L..9L]|>Seq.iter(fun n->rcGf n|>Seq.skip 85|>Seq.take 15|>Seq.iter(printf "%d ");printfn "");printfn "#####"

[1L..9L]|>Seq.iter(fun n->rcGf n|>Seq.skip 990|>Seq.take 10|>Seq.iter(printf "%d ");printfn "");printfn "#####"

{{out}}

<pre>

</pre>

=={{header|Factor}}==

math.functions math.ranges math.text.utils prettyprint sequences ;

IN: rosetta-code.palindromic-gapful-numbers

15 100 ! part 2

10 1000 ! part 3 (Optional)

{{out}}

<pre style="height:45ex">

=={{header|FreeBASIC}}==

Time-consuming brute-force solution with only a few speedups...

if n<100 then return false

dim as string ns = str(n)

print_range(yays(), 1, 20)

print_range(yays(), 86, 100)

{{out}}

<pre>

=={{header|Fōrmulæ}}==

 

 

=={{header|Go}}==

 

To keep the Pascal entry company, I've extended the search to the first 10 million such numbers for each of the nine sets.

 

import "fmt"

fmt.Println()

}

 

{{out}}

=={{header|Haskell}}==

===Brute Force===

 

palindromic :: Int -> Bool

putStrLn "\nLast 10 of first 1000 palindromic gapful numbers ending in:"

showSets (show . drop 990 . take 1000 . result)

 

===Optimized===

Here the approach is to generate a series of palindromes.

import Control.Monad (guard)

 

, ("Last 15 of first 100", drop 85 . take 100)

, ("Last 10 of first 1000", drop 990 . take 1000)

{{out}}

<pre>

</pre>

Part 2:

palindromify=: [: , ((,~ |.@}.) ; (,~ |.))&>

gapful=: (0 = (|~ ({.,{:)&.(10&#.inv)))&>

task2_palindromes=: [: 10&#.&> [: palindromify task2_cartesian_products

task2_gapfuls=: [: /:~ [: ; [: (#~ gapful)@task2_palindromes&.> >:@i.

 

<pre>

 

=={{header|Java}}==

import java.util.ArrayList;

import java.util.HashMap;

 

}

 

{{out}}

 

=={{header|Julia}}==

 

struct Palindrome x1::UInt8; x2::UInt8; outer::UInt8; end

 

testpal()

<pre style="height:100ex;overflow:scroll">

Last digit | Last 20 of 20 palindromic gapful numbers from 100

1770.411549 seconds (13.02 G allocations: 443.799 GiB, 40.12% gc time)

</pre>

 

=={{header|Nim}}==

Forms palindromes using number<->string conversions.

 

import times # for timing code execution

import unicode # for reversed

for digit in 1..9: echo(digit, " : ", palindromicgapfuls(digit, count, keep) )

 

 

Compil: $ nim c --cc:gcc --d:danger palindromicgapfuls.nim

Run as: $ ./palindromicgapfuls

Faster version performing number<->string conversions for palindromes.

 

import times # for timing code execution

import unicode # for reversed

for digit in 1..9: echo(digit, " : ", palindromicgapfuls(digit, count, keep) )

 

 

Compil: $ nim c -d:danger -d:lto --passC:-march=native palindromicgapfuls.nim

Run as: $ ./palindromicgapfuls

Fastest: make palindromes directly numerically.

 

proc make_palindrome(front_half: uint64, power: int): uint64 =

while front_half > 0:

front_half = front_half div 10

 

proc palindromicgapfuls(digit, count, keep: int): seq[uint64] =

let to_skip = count - keep # count of unwanted values to skip

var gapfuls = newSeq[uint64]() # array of palindromic gapfuls

while true:

if (power.inc; power and 1) == 0: base = base * 10

var this_lo = base * digit # starting half for this digit: 10.. to 90..

var next_lo = base * (digit + 1) # starting half for next digit: 20.. to 100..

let basep = if (power and 1) == 1: base11 else: base

for _ in 0..9:

if gapfuls.len >= keep: return gapfuls[0..keep-1]

 

let start = epochTime()

for digit in 1..9: echo(digit, " : ", palindromicgapfuls(digit, count, keep) )

 

 

Compil: $ nim c --cc:gcc --d:danger palindromicgapfuls.nim

Run as: $ ./palindromicgapfuls

{{out}}

<pre>First 20 palindromic gapful numbers ending with:

9 : 968787783387787869</pre>

 

{$IFDEF FPC}

{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$CODEALIGN proc=16}{$ALIGN 16}

OutPalinGap(10000000,10000000,dgt);

writeln;

palindromic gapful numbers from 1 to 20

1 : 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591

real 0m4,503s

</pre>

 

=={{header|Phix}}==

{{trans|Go}}

Translation of Go, but trimmed back to bare minimum: you should not expect this to fare particularly well at the 10_000_000-level against the likes of Go/Pascal, though it should fare reasonably well against lesser beings... The version below beats 'em all, though, for now.

{{out}}

<pre style="font-size: 11px">

</pre>

 

{{out}}

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

Completed in 0.7s

</pre>

spare time you have, leave this running and it'll look better, uncomment the reset of

count, to something that'll actually finish, and you'll start to believe. :-)

while count do

count -= 1

?collect(9,count,1)

 

=={{header|Prolog}}==

{{works with|SWI Prolog}}

Next is Digit * 10 - 1.

 

print_numbers(1, 20, Numbers),

print_numbers(86, 100, Numbers),

 

{{out}}

Note: Although this uses the idea of generating palindromes from the Geeks4geeks reference mentioned in the Factor entry, none of their code was used.

 

from pprint import pformat

import re

b = {k:v[-last:] for k, v in bin.items()}

txt = pformat(b, width=220)

 

{{out}}

 

===Functional===

 

from itertools import chain, count, islice, tee

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>First 20 samples of gapful palindromes (> 100) by last digit:

{{works with|Rakudo|2019.07.1}}

 

 

# Infinite lazy iterator to generate palindromic "gap" numbers

my @gappal = (1..9).map: -> \digit {

my \divisor = digit + 10 * digit;

}

 

put "$_: " ~ @gappal[$_-1][|$range].fmt("%{$fmt}s") for 1..9;

say round( now - $now, .001 ), " seconds";

{{out}}

<pre style="font-size:80%;">(Required) First 20 gapful palindromes:

 

=={{header|REXX}}==

/*─────────────────────── palindromic gapful numbers listed by their last decimal digit.*/

numeric digits 20 /*ensure enough decimal digits gapfuls.*/

do k=1 for 9; say k':' strip( subword($.k, 1 + n - z) )

end /*k*/; say

{{out|output|text=&nbsp; when using the internal default inputs:}}

 

 

=={{header|Ring}}==

load "stdlib.ring"

 

 

see "done..." + nl

Output:

<pre>

{{trans|Crystal}}

===Brute force and slow===

r1 = digit * (10**pow + 1)

r2 = 10**pow * (digit + 1)

count = 1000

puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:"

 

===Orders of Magnitude Faster: Direct Generation of Numbers===

Run as: $ ruby palindromicgapfuls.rb

Optimized version, the ultimate fastest: Ruby 2.7.1 - 112.5 secs

gapfuls = [] # array of palindromic gapfuls

nn = digit * 11 # digit gapful divisor: 11, 22,...88, 99

1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }

 

 

Compact version: Ruby-2.7.1 - 113.0 secs

gapfuls = [] # array of palindromic gapfuls

nn = digit * 11 # digit gapful divisor: 11, 22,...88, 99

1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }

 

 

Object Oriented implementation: Ruby 2.7.1 - 113.0 secs

include Enumerable

 

1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }

 

 

Versions optimized for minimal memory use: Ruby 2.7.1 - 110.0 secs

palcnt = 0 # count of gapful palindromes

to_skip = count - keep # count of unwanted values to skip

1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

 

 

Compact version optimized for minimal memory use: Ruby 2.7.1 - 111.5 secs

palcnt = 0 # count of gapful palindromes

to_skip = count - keep # count of unwanted values to skip

1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

 

 

OOP version optimized for minimal memory use: Ruby 2.7.1 - 116.0 secs

<BR>It creates an output method that skips the unwanted values and only keeps/stores the desired ones.

include Enumerable

 

1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }

 

{{out}}

<pre>First 20 palindromic gapful numbers 100 ending with:

{{trans|F#}}

0.186s on Intel(R) Core(TM) i5-1035G1 CPU @ 1.00GHz

class PalNo

def initialize(set)

for n in 1..9 do palNo=PalNo.new(n); g=1; palNo.each{|n| print "#{n} " if g>85; g+=1; break unless g<101}; puts "" end; puts "####"

for n in 1..9 do palNo=PalNo.new(n); g=1; palNo.each{|n| print "#{n} " if g>990; g+=1; break unless g<1001}; puts "" end; puts "####"

{{out}}

<pre>

Run as: $ ruby fsharp2ruby.rb

Best Time: 437.566515299 secs

def initialize(digit)

@digit, @l, @dd = digit, 3, 11*digit

(1..9).each { |digit| PalNo.new(digit).show(10_000_000, 1) }; puts "####"

 

{{out}}

<pre>

This version uses number->string then string->number conversions to create palindromes.

 

let mut palcnt = 0u64; // count of gapful palindromes

let to_skip = count - keep as u64; // count of unwanted values to skip

println!("{:?}", t.elapsed())

System: I7-6700HQ, 3.5 GHz, Linux Kernel 5.9.10, Rust 1.48

Compil: $ rustc -C opt-level=3 -C target-cpu=native -C codegen-units=1 -C lto palindromicgapfuls.rs

About 2.5x faster.

 

let mut palcnt = 0u64; // count of gapful palindromes

let to_skip = count - keep as u64; // count of unwanted values to skip

println!("{:?}", t.elapsed())

System: I7-6700HQ, 3.5 GHz, Linux Kernel 5.9.10, Rust 1.48

Compil: $ rustc -C opt-level=3 -C target-cpu=native -C codegen-units=1 -C lto palindromicgapfuls.rs

=={{header|Sidef}}==

Inspired from the C++ and Raku entries.

 

has power = base

say ("#{d}: ", arr.map{ "%*s" % (w, _) }.join(' '))

}

{{out}}

<pre style="font-size:83%">

{{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.

 

var reverse = Fn.new { |s|

}

System.print()

 

{{out}}

8: 80869644696808 80869655696808 80869666696808 80869677696808 80869688696808

9: 96877711777869 96877800877869 96877899877869 96877988977869 96878077087869

</pre>

 

=={{header|zkl}}==

Using ideas from the Factor entry

// 10,False --> 1001,1111,1221,1331,1441,1551,1661,1771,1881,..

fcn createPalindromeW(start,oddLength){ //--> iterator

if(p%10==endsWith and (p%div)==0) p else Void.Skip

})

[1..9].apply(palindromicGapfulW).apply("walk",20) : pgpp(_);

 

m,fmt := (0).max(table.apply((0).max)).numDigits, "%%%dd ".fmt(m).fmt;

foreach d,row in ([1..].zip(table)){ println(d,": ",row.pump(String,fmt)) }

{{out}}

<pre style="font-size:83%">

9: 9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869

</pre>

* (3 min to 48sec) with 8 cores (Intel 4/4).

*/

.apply("noop") // wait for threads to finish

: pgpp(_);

{{out}}

<pre style="font-size:83%">