sporeball numbers

Background

We've studied at least five different types of numbers based on the IDs of different users on this site. Why not study another?

My user ID is $$\91030_{10}\$$. Its binary representation is $$\10110001110010110_2\$$, a representation which has an interesting property of its own:

• One option for the longest palindromic run of binary digits is $$\0011100\$$.
• If you remove this run of digits, the remaining list of digits ($$\1011010110\$$) can be split into two identical halves.

I define a sporeball number as any positive integer where at least one of the options for the longest palindromic run of digits in its binary representation can be removed such that the remaining list of digits can be split into two identical halves.

Write a program or function which takes a positive integer as input and determines whether or not it is a sporeball number.

Some clarifications to keep in mind:

• Leading zeroes should be ignored.
• Exactly one palindromic run of digits should be removed before checking if the remaining digits can be split into identical halves.
• If one of the options for the longest palindromic run occurs multiple times, remove only one occurrence, rather than all of them, before checking if the remaining digits can be split into identical halves.
• Single digits are palindromic.
• The empty string "" is not palindromic, and cannot be split into two identical halves.

Remember that there may be more than one longest palindromic run of digits:

• The binary digits of $$\12_{10}\$$ ($$\1100\$$) contain two options for the longest palindromic run ($$\11\$$ and $$\00\$$). No matter which one is removed, the remaining digits will be able to be split into identical halves. Thus, $$\12_{10}\$$ is a sporeball number.
• The binary digits of $$\20_{10}\$$ ($$\10100\$$) contain two options for the longest palindromic run ($$\010\$$ and $$\101\$$). Removing $$\010\$$ leaves the digits $$\10\$$, which cannot be split into identical halves; however, removing $$\101\$$ leaves the digits $$\00\$$, which can be. Thus, $$\20_{10}\$$ is a sporeball number.

There are 153 sporeball numbers under 1,000:

12 20 23 24 26 28 29 39 48 57 60 68 71 84 87 96 100 106 108 110 111 113 117 123 124 132
135 154 166 178 180 183 192 204 207 210 222 225 237 240 243 252 260 263 277 282 287 295
314 326 334 336 337 340 343 348 351 354 370 372 375 384 392 394 396 399 404 412 418 426
428 431 432 446 449 457 469 476 477 479 480 483 484 490 491 496 497 501 503 508 516 519
533 538 543 562 600 610 612 615 634 646 652 660 663 664 670 673 676 691 700 703 706 718
720 735 742 754 756 759 768 778 780 783 792 804 816 821 826 828 831 834 858 870 874 876
879 894 897 918 921 922 924 927 933 957 960 963 972 978 987 993 999


Rules

• This is , so shortest answer in bytes wins.
• Standard I/O rules apply.
• Nice name. I’m afraid I’ll never have a set of numbers named after me
– user
Sep 19 '20 at 3:39
• @JoKing The empty string is not palindromic because it contains no characters to read backwards or forwards. Sep 19 '20 at 4:24
• "You can use any two distinct values for true and false." - this is not the site default of truthy/falsey (which allows values which the language evaluates as true/false). I don't think there is a good reason to override this default here. Sep 19 '20 at 15:17
• FWIW the empty string is palindromic, by definition, since it's the same forwads as it is backwards. It will never be the longest present, however (since, as you point out, single digits are palindromic). Sep 19 '20 at 15:26
• Does "exactly one palindromic run of of digits" mean all instances of a single palindrome, or one instance of a palindrome? The least number where this makes a difference is 2405.
– att
Sep 21 '20 at 5:08

Brachylog, 26 bytes

{ḃ~c₃↺{↔?¬Ė}ʰ↻c}ᶠlᵒlᵍh∋~jz


Try it online!

Dreadfully slow for large falsy testcases, but verifies truthy ones surprisingly quickly. My original solution ran into the same false negatives as xash's deleted answer, but fortunately the process of fixing that helped me shave off 2 bytes.

{              }ᶠ             Find every possible result from:
ḃ                             take the binary digits of the input,
~c₃                          split them into three (possibly empty) partitions,
↺{    }ʰ↻                 for the middle partition:
↔                        reversed it is
?                       itself
¬Ė                     which is not the empty list;
Ė                     replace it with the empty list.
c                and re-concatenate the partitions.
lᵒ           Sort the results by length,
lᵍ         group them by length,
h        and take the first group (that with minimal length).
∋       Some element of that group
~j     is something concatenated with itself
z    which is not the empty list.


Rather than maximize the length of the palindromic substring, it just minimizes the length of everything left, which is an approach I really only came up with because of my initial approach of relying on ≜.

05AB1E, 47454342404140 31 bytes

b©ŒʒÂQ}é.γg}θε®sõ.;D2ä1ìËsgĀ*}à


Try it online!

-2 thanks to @ovs!
-1 thanks to @ovs!
-1 (lol) thanks to a bug fix
-1 thanks to @ovs (again!)
+1 due to challenge clarification :-(
but -1 thanks to @Kevin!
and another whopping -9 thanks to @Kevin!

Don't mind me... just posting another overly long answer in 05AB1E that will probably be was golfed by anyone experienced with 05AB1E.

The ÂQ trick to see if a string is a palindrome was taken from this 05AB1E tip answer by Kevin.

Explained (old)

bDV.œ˜ʒÂQ} Ð€gàUʒgXQ}εYsõ:Ðg;ôËsgD0ÊsÈ**}à
bDV                                             # Get the binary representation of the input, and assign variable Y to that value while still keeping a copy on the stack
.œ                                           # Push all partitions of that binary representation
˜                                          # Flatten said list and
ʒ                                         #  Select items where:
ÂQ}                                      #      They are a palindrome

Ð                                   # and push three copies of it to the stack.
€g                                 # For one of those copies, push the length of each item
àU                               # Find the maximum length and assign it to variable Y
ʒgXQ}                          # From the list of palindromic partitions, select the ones which are of the maximum length
ε                         # And from that list:
Ysõ:                     #   Replace the occurrence of that number in variable Y with nothing THEN
Ð                    #   Triplicate it THEN
g;ô                 #   Split it in half THEN
Ë                #   See if all elements are equal AND
sgD0ÊsÈ**       #   Ensure the length of Y with the item removed isn't 0 and isn't odd
}à     # Close the map, and take the maximum of the list and implicitly print the result

• time to do this in Keg Sep 19 '20 at 5:34
• I think you can replace O>≠ with à (maximum), because the list only contains 1s and 0s at the end. And if you flatten the partitions before checking for palindromes, the map isn't necessary.
– ovs
Sep 19 '20 at 7:12
• @sporeball fixed Sep 19 '20 at 20:50
• Since : performs infinite replacement, this also fails on an input of 2405. Sep 21 '20 at 6:31
• 31 bytes: DV...Y to ©...®; .œ˜ to Œ; Ð€gàUʒgXQ} to é.γg}θ; ËsgƵ2SQË* to 1ìËsgĀ*. Sep 21 '20 at 7:44

J, 8078756661 57 bytes

1 e.#\,@((#<.[-:[:,~,~inv)\.*[:(*i.@#=+./"{i:1:)(-:|.)\)]


Try it online!

-3 bytes thanks to Marshall

-9 bytes thanks to xash

Tougher than I thought it would be.

Finally a respectable size, though still high for J.

J, alternate approach, 73 bytes

1 e.1}.((((<:@[,(-:|.)\#(#<.]-:[:,~,~inv)\.)~{.))^:(0<{.@]*1=#@])^:_#)@#:


Try it online!

This one uses do..while ^:(while)^:_, starting by searching the longest possible length palindrome, and stopping as soon as it finds any for a certain length, returning the boolean telling you if the complement for that palindrome is a doubled string.

• … and [:(*i.@#=1 i:~+./"1) still feels too long. But \  and \. are a nice fit for this challenge!
– xash
Sep 20 '20 at 3:01
• 66 bytes
– xash
Sep 20 '20 at 3:35
• @xash, thanks! now 61: tio.run/… Sep 20 '20 at 3:39
• @xash fwiw I spent some time trying to improve *i.@#=+./"{i:1: but wasn't able to. Sep 20 '20 at 6:18

Retina, 126 bytes

.+
*
+^(_*)\1(_?)(?!^|_)
$1$.2
Lv$(.)+.?(?<-1>\1)+(?(1)(?!))|.$$' N$
$.& +m^((.)*)¶(?<-2>.)*(?(2)(?!)).+$
$1 0m^(.+)\1$


Try it online! Explanation:

.+
*


Convert the input to unary.

+^(_*)\1(_?)(?!^|_)
$1$.2


Convert it to binary.

Lv$(.)+.?(?<-1>\1)+(?(1)(?!))|.$$'  Find and remove palindromes. N$
$.&  Sort the results by length, so that the first result corresponds to the longest palindrome. +m^((.)*)¶(?<-2>.)*(?(2)(?!)).+$
$1  Remove all results of longer length. 0m^(.+)\1$


Check whether any of them can be split.

• I've since noticed that taking input directly as a binary string is allowed; this would naturally cut the byte count by 32 if applied here (simply delete the first four lines).
– Neil
Sep 20 '20 at 17:39

Charcoal, 53 bytes

≔⍘Ｎ²θＦ⊕ＬθＦιＦ⁼✂θκι¹⮌✂θκι⊞υ⁺…θκ✂θι¿⌊υ⊙υ∧⁼Ｌι⌊ＥυＬλ⁼ι×²∕ι²


Try it online! Link is to verbose version of code. Output is a Charcoal boolean, i.e. - for a sporeball number, empty if not. Explanation:

≔⍘Ｎ²θ


Convert the input to base 2.

Ｆ⊕ＬθＦι


Loop over all nontrivial substrings of the input.

Ｆ⁼✂θκι¹⮌✂θκι


If this substring equals its reverse...

⊞υ⁺…θκ✂θι


... then push the remaining digits to the predefined empty list.

¿⌊υ


If the original number was not palindromic, ...

⊙υ∧⁼Ｌι⌊ＥυＬλ⁼ι×²∕ι²


... then output whether any of the results are of minimal length and equal themselves halved in length and doubled again.

• Taking the input directly as a binary string would naturally save 5 bytes.
– Neil
Sep 20 '20 at 17:39

Jelly, 31 bytes

ḊḢŒḂḤœP⁸F
BØ2jŒṖḟ€€2Ç€LÐṂŒHE$ƇẸ  Try it online! Or see those up to 600 (up to 1000 is too slow). How? BØ2jŒṖḟ€€2Ç€LÐṂŒHE$ƇẸ - Main Link: n
B                     - convert (n) to a binary list
Ø2                   - [2,2]
j                  - join ([2,2]) with (B(n))
ŒṖ                - partitions (none with empty parts, hence the Ø2j and ḟ€€2)
ḟ€€2            - remove any 2s from each part of each
Ç€          - call Link 1 for each
(removes second part if it's palindromic & flattens)
LÐṂ       - keep only those with minimal length
Ƈ  - filter keep those for which:
$- last two links as a monad: ŒH - split into two E - all equal? Ẹ - any truthy? ḊḢŒḂḤœP⁸F - Link 1: list of parts Ḋ - deueue Ḣ - head -> second part ŒḂ - is palindromic? (1 if so, else 0) Ḥ - double ⁸ - the list of parts œP - partition at index (0œP[4,5,6,7] -> [[4,5,6,7]] while 2œP[4,5,6,7] -> [[4],[6,7]]) F - flatten  Wolfram Language (Mathematica), 128...103 101 bytes FreeQ[MinimalBy[$@@d~Drop~#&/@SequencePosition[d=#~IntegerDigits~2,_?PalindromeQ],Length],a__~$~a__]&  Try it online! Returns False if the number is not a sporeball number, and True otherwise. d=#~IntegerDigits~2 (* get digits of input, base 2. *) SequencePosition[ % ,_?PalindromeQ] (* get positions of palindromic runs *) d~Drop~#/@ % (* and remove them, *)$@@ %                                   (* placing the remaining digits in $*) MinimalBy[ % ,Length] (* keep the shortest remaining digit lists *) FreeQ[ % ,a__~$~a__]                    (* and check if they have identical halves. *)


$@@ is needed to handle cases like $$\38=100110_2\$$, where removing either of the two longest-palindromes 1001, 0110 has the same result 10. JavaScript (ES6), 175 bytes n=>(m=g=(s,p='',q=p)=>s?g(s.slice(1),p+s[0],q,s==[...s].reverse(L=s.length).join?o=(L<=m?o:!(m=L))|L==m&/^(.+)\1$/.test(p+q):0,g(s.slice(0,-1),p,s[L-1]+q)):o)(n.toString(2))


Try it online!

Commented

n => (                    // n = input
m =                     // initialize m to a non-numeric value
g = (                   // g is a recursive function taking:
s,                    //   s = middle part of the string (the palindromic one)
p = '', q = p         //   p = left part, q = right part
) =>                    //
s ?                   // if s is not empty:
g(                  //   outer recursive call:
s.slice(1),       //     with the first character of s removed ...
p + s[0],         //     ... and appended to p
q,                //     with q unchanged
s == [...s]       //     split s
.reverse(         //     reverse it
L = s.length    //     set L = length of s (argument ignored by reverse)
).join ?        //     join again; if s is a palindrome:
o =             //       update o:
( L <= m ?    //         if L is not higher than m:
o         //           yield o
:           //         else:
!(m = L)  //           update m to L and yield 0
) | L == m &  //         bitwise OR with 1 if L = m (current max.)
/^(.+)\1$/ // and the concatenation of p and q can be .test(p + q) // split into 2 identical halves : // else: 0, // abort g( // inner recursive call: s.slice(0, -1), // with the last character of s removed p, // with p unchanged s[L - 1] + q // with the last character of s prepended to q ) // end of inner recursive call ) // end of outer recursive call : // else: o // return o )(n.toString(2)) // initial call to g with s = binary string for n  Husk, 28 bytes ▲foE½†!ḋ¹ṠM-ö→kLfoS=↔m!ḋ¹Qŀḋ  Try it online! Returns an empty list (which is falsy in Husk) or a nonempty list (which is truthy). Explanation The repeated ḋ feels wasteful but I'm not sure how to get rid of it. Input is a number, say n=357 ▲f(E½)†!ḋ¹ṠM-(→kLf(S=↔m!ḋ¹)Q)ŀḋ Parentheses added for clarity. ḋ Binary digits: D=[1,0,1,1,0,0,1,0,1] ŀ Indices: I=[1,2,3,4,5,6,7,8,9] (→kLf(S=↔m!ḋ¹)Q) Get indices of longest palindromic runs. Q Slices: [[1],[2],[1,2],..,[1,2,..,9]] f Filter by condition: (S=↔m!ḋ¹) Is a palindrome in D. m Map ! indexing into ḋ¹ D (recomputed). S= That equals ↔ its reverse. kL Classify (into separate lists) by length. → Get the last one: [[2,3,4,5],[4,5,6,7]] ṠM- Remove each from I: [[1,6,7,8,9],[1,2,3,8,9]] † Deep map !ḋ¹ indexing into D (recomputed again): [[1,0,1,0,1],[1,0,1,0,1]] f Filter by condition: (E½) Splits into identical halves. ½ Split into halves (if length is odd, first part is longer): [[1,0,1],[0,1]] E All elements are equal: 0 Result is [] ▲ Maximum, or [] if the argument is empty: [] The final result is nonempty iff the last filter keeps a nonempty list.  Pip-p, 62 bytes $Q_^@#_/2FIMN(_FI#*Y{c:y@$,:acQRVc?yRAaxx}M$ALCG1+#YTBa)=#_FIy


Outputs an empty list for falsey, non-empty for truthy. Try it online!

Oy vey. I'm not going to write up a detailed explanation for that monstrosity. Suffice it to say that half the bytecount (roughly the Y{c:y@$,:acQRVc?yRAaxx}M$ALCG1+# section) is required to find all palindromic substrings and remove them.

• I want to try writing an explanation for this. May 1 at 8:16
• @Razetime Hey, go for it! May 1 at 16:17

Python 3.8 (pre-release), 154 152 bytes

def f(n):s=f'{n:b}';k=len(s);return max((b-a,(r:=s[:a]+s[b:])[:(h:=k-b+a>>1)]==r[h:]>'')for a in range(k)for b in range(a,k+1)if(p:=s[a:b])==p[::-1])[1]


Try it online!

Commented:

s=f'{n:b}'                    # convert n to a binary string
k=len(s)                      # and take the length
return max( ... )[1]          # the second element from the maximum of
(b-a,                       #   tuples of palindrome length b-a ...
[:(h:=k-b+a>>1)] #   ... and is the first half
(r:=s[:a]+s[b:])            #       of the binary string without the palindrome
==r[h:]                   #       equal to the second half
>'')                      #       and not equal to the empty string
for a in range(k)           #   for palindrome starting positions a in [0, 1, ..., k-1]
for b in range(a,k+1)       #   for palindrome end indices b in [1, 2, ..., k-a]
if(p:=s[a:b])==p[::-1])     #   if this is an actual palindrome


If there multiple palindromes of same maximum length, max selects the tuple with the highest second value, where True>False.

Factor, 209 197 bytes

: s ( n -- ? ) >bin dup all-subseqs [ dup reverse = ] filter
dup [ last length ] dip [ length over = ] filter nip
[ split1 append [ ""= not ] keep dup length 2/ cut = and ]
with [ or ] map-reduce ;


Try it online!

Japt, 33 42 bytes

s2
ã fêS üÊo


Try it

s2          - convert input to binary string

ã           - substrings
fêS       - filter palindrome
üÊo   - take last group by length

Vc@ðXÃ      - find indexes of each palindrome in input
£jXVÎlÃ     - map those indexes by removing n(=palindr.length) characters from input at index
®òZÊ/2Ã     - split all results
d_          - return true if any :
ZÎ¥Zo     - are ==

• Fixed : now works for numbers with more identical longest palindromic runs like 2405 => 100101100101

• Test : computes first 1000 terms and check if the result is the same as test cases.

• fails on 2405
– att
Sep 21 '20 at 2:54
• On second thought, the spec is a little vague about that. I'll ask.
– att
Sep 21 '20 at 5:07
• @att I think you are right , that's why r replaces every occurrences of X, hence 100101100101 becomes 0101 which gives true, I think OP clearly stated that exactly one run have to be discarded. Thanks for spotting that out. Sep 21 '20 at 5:45

Dotty, 201 bytes

s=>((for{j<-1 to s.size
i<-0 to j-1
x=s.slice(i,j)if x==x.reverse}yield(i,j))groupBy(_-_)minBy(_._1)_2)exists{(i,j)=>val x=s.slice(0,i)+s.substring(j)
x!=""&&x.slice(0,x.size/2)==x.substring(x.size/2)}


Try it online (in Scastie)

Input must already be a binary string.

Dotty, 226 bytes

x=>{val s=x.toBinaryString
((for{j<-1 to s.size
i<-0 to j-1
x=s.slice(i,j)if x==x.reverse}yield(i,j))groupBy(_-_)minBy(_._1)_2)exists{(i,j)=>val x=s.slice(0,i)+s.substring(j)
x!=""&&x.slice(0,x.size/2)==x.substring(x.size/2)}}


Try it online (in Scastie)

Input is an Int.