Distinct palindromes within decimal numbers
Find all distinct palindromes contained as substrings in decimal representation of n. Note that for the purpose of the initial function, a single digit will be considered a palindrome.
- Task
- Find all the palindromes including single digits in the integers from 100 to 125, inclusive.
- Determine which if any of the following decimal integers contain palindromes of 2 digits or more:
9, 169, 12769, 1238769, 123498769, 12346098769, 1234572098769, 123456832098769, 12345679432098769, 1234567905432098769, 123456790165432098769, 83071934127905179083, 1320267947849490361205695
- Also see
-
- OEIS entry: A262188 (Task 1).
- OEIS entry: A151997 (Task 2).
Palindrome_detection
Longest_palindromic_substrings
N_1's_followed_by_a_3
Factor
<lang factor>USING: formatting io kernel math math.ranges present prettyprint sequences sequences.extras sets ;
- dpal ( n -- seq )
present all-subseqs members [ dup reverse = ] filter ;
! task 1 "Number Palindromes" print 100 125 [a..b] [ dup pprint bl bl bl bl bl dpal . ] each nl
! task 2 "Number Has no >= 2 digit-palindromes?" print { 9 169 12769 1238769 123498769 12346098769 1234572098769
123456832098769 12345679432098769 1234567905432098769 123456790165432098769 83071934127905179083 1320267947849490361205695 }
[ dup dpal [ length 2 < ] reject empty? "%-25d %u\n" printf ] each</lang>
- Output:
Number Palindromes 100 { "1" "0" "00" } 101 { "1" "0" "101" } 102 { "1" "0" "2" } 103 { "1" "0" "3" } 104 { "1" "0" "4" } 105 { "1" "0" "5" } 106 { "1" "0" "6" } 107 { "1" "0" "7" } 108 { "1" "0" "8" } 109 { "1" "0" "9" } 110 { "1" "0" "11" } 111 { "1" "11" "111" } 112 { "1" "2" "11" } 113 { "1" "3" "11" } 114 { "1" "4" "11" } 115 { "1" "5" "11" } 116 { "1" "6" "11" } 117 { "1" "7" "11" } 118 { "1" "8" "11" } 119 { "1" "9" "11" } 120 { "1" "2" "0" } 121 { "1" "2" "121" } 122 { "1" "2" "22" } 123 { "1" "2" "3" } 124 { "1" "2" "4" } 125 { "1" "2" "5" } Number Has no >= 2 digit-palindromes? 9 t 169 t 12769 t 1238769 t 123498769 t 12346098769 t 1234572098769 t 123456832098769 t 12345679432098769 t 1234567905432098769 t 123456790165432098769 t 83071934127905179083 t 1320267947849490361205695 f
Julia
<lang julia>function allpalindromes(a::Vector{T}) where T
pals = Vector{Vector{T}}([[x] for x in a]) len = length(a) len < 2 && return pals a == reverse(a) && push!(pals, a) len == 2 && return pals for i in 2:len left = a[1:i] left == reverse(left) && push!(pals, left) end return unique(vcat(pals, allpalindromes(a[2:end])))
end
println("Number Palindromes") for n in 100:125
println(" ", rpad(n, 7), sort(allpalindromes(digits(n))))
end
palindrome2plusfree(n) = (a = allpalindromes(digits(n)); all(x -> length(x) == 1, a))
println("\nNumber Has no >= 2 digit palindromes") for n in [9, 169, 12769, 1238769, 123498769, 12346098769, 1234572098769, 123456832098769,
12345679432098769, 1234567905432098769, 123456790165432098769, 83071934127905179083, 1320267947849490361205695] println(rpad(n, 26), palindrome2plusfree(n))
end
</lang>
- Output:
Number Palindromes 100 [[0], [0, 0], [1]] 101 [[0], [1], [1, 0, 1]] 102 [[0], [1], [2]] 103 [[0], [1], [3]] 104 [[0], [1], [4]] 105 [[0], [1], [5]] 106 [[0], [1], [6]] 107 [[0], [1], [7]] 108 [[0], [1], [8]] 109 [[0], [1], [9]] 110 [[0], [1], [1, 1]] 111 [[1], [1, 1], [1, 1, 1]] 112 [[1], [1, 1], [2]] 113 [[1], [1, 1], [3]] 114 [[1], [1, 1], [4]] 115 [[1], [1, 1], [5]] 116 [[1], [1, 1], [6]] 117 [[1], [1, 1], [7]] 118 [[1], [1, 1], [8]] 119 [[1], [1, 1], [9]] 120 [[0], [1], [2]] 121 [[1], [1, 2, 1], [2]] 122 [[1], [2], [2, 2]] 123 [[1], [2], [3]] 124 [[1], [2], [4]] 125 [[1], [2], [5]] Number Has no >= 2 digit palindromes 9 true 169 true 12769 true 1238769 true 123498769 true 12346098769 true 1234572098769 true 123456832098769 true 12345679432098769 true 1234567905432098769 true 123456790165432098769 true 83071934127905179083 true 1320267947849490361205695 false
Phix
procedure show_all_palindromes(string s, integer longest=0) sequence res = {} for i=1 to length(s) do if longest=0 then res = append(res,{1,s[i..i]}) end if for j=0 to iff(i>1 and s[i-1]=s[i]?2:1) do integer rev = j, fwd = 1 while rev<i and i+fwd<=length(s) and s[i-rev]=s[i+fwd] do if longest=0 then res = append(res,{rev+fwd+1,s[i-rev..i+fwd]}) end if rev += 1 fwd += 1 end while if longest>0 then longest = max(longest,rev+fwd-1) end if end for end for if longest then printf(1,"%-26s %t\n",{s,longest<3}) else printf(1," %s %s\n",{s,join(vslice(unique(res),2))}) end if end procedure printf(1,"Number Palindromes\n") papply(apply(true,sprintf,{{"%d"},tagset(125,100)}),show_all_palindromes) constant tests = split_any("""9, 169, 12769, 1238769, 123498769, 12346098769, 1234572098769, 123456832098769, 12345679432098769, 1234567905432098769, 123456790165432098769, 83071934127905179083, 1320267947849490361205695"""," ,\n") printf(1,"\nNumber Has no >2 digit palindromes\n") papply(true,show_all_palindromes,{tests,1})
- Output:
Number Palindromes 100 0 1 00 101 0 1 101 102 0 1 2 103 0 1 3 104 0 1 4 105 0 1 5 106 0 1 6 107 0 1 7 108 0 1 8 109 0 1 9 110 0 1 11 111 1 11 111 112 1 2 11 113 1 3 11 114 1 4 11 115 1 5 11 116 1 6 11 117 1 7 11 118 1 8 11 119 1 9 11 120 0 1 2 121 1 2 121 122 1 2 22 123 1 2 3 124 1 2 4 125 1 2 5 Number Has no >2 digit palindromes 9 true 169 true 12769 true 1238769 true 123498769 true 12346098769 true 1234572098769 true 123456832098769 true 12345679432098769 true 1234567905432098769 true 123456790165432098769 true 83071934127905179083 true 1320267947849490361205695 false
Raku
A minor modification of the Longest palindromic substrings task. As such, works for any string, not just integers. <lang perl6>use Sort::Naturally;
sub getpal ($str) {
my @chars = $str.comb; my @pal = flat @chars, (1 ..^ @chars).map: -> \idx { my @s; for 1, 2 { my int ($rev, $fwd) = $_, 1; loop { quietly last if ($rev > idx) || (@chars[idx - $rev] ne @chars[idx + $fwd]); $rev = $rev + 1; $fwd = $fwd + 1; } @s.push: @chars[idx - $rev ^..^ idx + $fwd].join if $rev + $fwd > 2; last if @chars[idx - 1] ne @chars[idx]; } next unless +@s; @s } @pal.unique.sort({.chars, .&naturally});
}
say 'All palindromic substrings including (bizarrely enough) single characters:'; put "$_ => ", getpal $_ for 100..125; put "\nDo these strings contain a minimum two character palindrome?"; printf "%25s => %s\n", $_, getpal($_).tail.chars > 1 for flat
9, 169, 12769, 1238769, 123498769, 12346098769, 1234572098769, 123456832098769, 12345679432098769, 1234567905432098769, 123456790165432098769, 83071934127905179083, 1320267947849490361205695, <Do these strings contain a minimum two character palindrome?></lang>
- Output:
All palindromic substrings including (bizarrely enough) single characters: 100 => 0 1 00 101 => 0 1 101 102 => 0 1 2 103 => 0 1 3 104 => 0 1 4 105 => 0 1 5 106 => 0 1 6 107 => 0 1 7 108 => 0 1 8 109 => 0 1 9 110 => 0 1 11 111 => 1 11 111 112 => 1 2 11 113 => 1 3 11 114 => 1 4 11 115 => 1 5 11 116 => 1 6 11 117 => 1 7 11 118 => 1 8 11 119 => 1 9 11 120 => 0 1 2 121 => 1 2 121 122 => 1 2 22 123 => 1 2 3 124 => 1 2 4 125 => 1 2 5 Do these strings contain a minimum two character palindrome? 9 => False 169 => False 12769 => False 1238769 => False 123498769 => False 12346098769 => False 1234572098769 => False 123456832098769 => False 12345679432098769 => False 1234567905432098769 => False 123456790165432098769 => False 83071934127905179083 => False 1320267947849490361205695 => True Do => False these => True strings => False contain => False a => False minimum => True two => False character => True palindrome? => False
REXX
This REXX version can handle strings or numbers, a hexadecimal string is included in the examples. <lang>/*REXX program finds distinct palindromes contained in substrings (of decimal numbers). */ parse arg LO HI mL $$ /*obtain optional arguments from the CL*/ if LO= | LO="," then LO= 100 /*Not specified? Then use the default.*/ if HI= | HI="," then HI= 125 /* " " " " " " */ if mL= | mL="," then mL= 2 /* " " " " " " */ if $$= | $$="," then $$= 9 169 12769 1238769 12346098769 1234572098769 123456832098769,
12345679432098769 1234567905432098769 123456790165432098769 , 83071934127905179083 'deadbeef' /* (hexadecimal) */ , 1320267947849490361205695 /* special numbers.*/
w= length(HI) /*max width of LO ──► HI for alignment.*/
do j=LO to HI; #= Dpal(j, 1) /*get # distinct palindromes, minLen=1 */ say right(j, w) ' has ' # " palindrome"s(#)': ' $ end /*j*/
w= length( word($$, words($$) ) ) /*find the length of the last special #*/ if words($$)==0 then exit 0 /*No special words/numbers? Then exit.*/ say
do j=1 for words($$); z= word($$, j) #= Dpal(z, mL); w= max(w, length(z) ) /*get # distinct palindromes, minLen=mL*/ _= left(':', #>0); @has= ' has '; @of='of length' say right(z, w) @has # " palindrome"s(#,,' ') @of mL "or more"_ space($) end /*j*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ s: if arg(1)==1 then return arg(3); return word( arg(2) 's', 1) /*──────────────────────────────────────────────────────────────────────────────────────*/ Dpal: procedure expose @. !. $ w; parse arg x, mL; $=; !.= 0; #= 0; L= length(x)
do j=1 for L /*test for primality for all substrings*/ do k=1 to L-j+1 /*search for substrings (including X).*/ y= strip( substr(x, j, k) ) /*extract a substring from the X string*/ if length(y)<mL | y\==reverse(y) then iterate /*too short or ¬palindromic?*/ if \!.y then do; $= $ right(y, w); !.y= 1; #= # + 1; end end /*k*/ end /*j*/ return #</lang>
- output when using the default inputs:
100 has 3 palindromes: 1 0 00 101 has 3 palindromes: 1 101 0 102 has 3 palindromes: 1 0 2 103 has 3 palindromes: 1 0 3 104 has 3 palindromes: 1 0 4 105 has 3 palindromes: 1 0 5 106 has 3 palindromes: 1 0 6 107 has 3 palindromes: 1 0 7 108 has 3 palindromes: 1 0 8 109 has 3 palindromes: 1 0 9 110 has 3 palindromes: 1 11 0 111 has 3 palindromes: 1 11 111 112 has 3 palindromes: 1 11 2 113 has 3 palindromes: 1 11 3 114 has 3 palindromes: 1 11 4 115 has 3 palindromes: 1 11 5 116 has 3 palindromes: 1 11 6 117 has 3 palindromes: 1 11 7 118 has 3 palindromes: 1 11 8 119 has 3 palindromes: 1 11 9 120 has 3 palindromes: 1 2 0 121 has 3 palindromes: 1 121 2 122 has 3 palindromes: 1 2 22 123 has 3 palindromes: 1 2 3 124 has 3 palindromes: 1 2 4 125 has 3 palindromes: 1 2 5 9 has 0 palindromes of length 2 or more 169 has 0 palindromes of length 2 or more 12769 has 0 palindromes of length 2 or more 1238769 has 0 palindromes of length 2 or more 12346098769 has 0 palindromes of length 2 or more 1234572098769 has 0 palindromes of length 2 or more 123456832098769 has 0 palindromes of length 2 or more 12345679432098769 has 0 palindromes of length 2 or more 1234567905432098769 has 0 palindromes of length 2 or more 123456790165432098769 has 0 palindromes of length 2 or more 83071934127905179083 has 0 palindromes of length 2 or more deadbeef has 1 palindrome of length 2 or more: ee 1320267947849490361205695 has 3 palindromes of length 2 or more: 202 494 949
Wren
<lang ecmascript>import "/seq" for Lst import "/fmt" for Fmt import "/sort" for Sort
var substrings = Fn.new { |s|
var ss = [] var n = s.count for (i in 0...n) { for (j in 1..n-i) ss.add(s[i...i + j]) } return ss
}
System.print("Number Palindromes") for (i in 100..125) {
var pals = [] var ss = substrings.call(i.toString) for (s in ss) { if (s == s[-1..0]) pals.add(s) } pals = Lst.distinct(pals) var cmp = Fn.new { |i, j| (i.count - j.count).sign } Sort.insertion(pals, cmp) // sort by length Fmt.print("$d $3s", i, pals)
}
var nums = [
"9", "169", "12769", "1238769", "123498769", "12346098769", "1234572098769", "123456832098769", "12345679432098769", "1234567905432098769", "123456790165432098769", "83071934127905179083", "1320267947849490361205695"
] System.print("\nNumber Has no >= 2 digit palindromes") for (num in nums) {
var ss = substrings.call(num).where { |s| s.count > 1 } var none = !ss.any { |s| s == s[-1..0] } Fmt.print("$-25s $s", num, none)
}</lang>
- Output:
Number Palindromes 100 1 0 00 101 1 0 101 102 1 0 2 103 1 0 3 104 1 0 4 105 1 0 5 106 1 0 6 107 1 0 7 108 1 0 8 109 1 0 9 110 1 0 11 111 1 11 111 112 1 2 11 113 1 3 11 114 1 4 11 115 1 5 11 116 1 6 11 117 1 7 11 118 1 8 11 119 1 9 11 120 1 2 0 121 1 2 121 122 1 2 22 123 1 2 3 124 1 2 4 125 1 2 5 Number Has no >= 2 digit palindromes 9 true 169 true 12769 true 1238769 true 123498769 true 12346098769 true 1234572098769 true 123456832098769 true 12345679432098769 true 1234567905432098769 true 123456790165432098769 true 83071934127905179083 true 1320267947849490361205695 false