sporeball numbers

Question

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.

Task

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 code-golf, so shortest answer in bytes wins.
• Standard I/O rules apply.

Answer 1

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

Answer 2

05AB1E, 47 45 43 42 40 41 40 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

Answer 3

J, ^{80 78 75 66 61} 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.

Answer 4

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.

Answer 5

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.

Answer 6

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

Answer 7

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.

Answer 8

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

Answer 9

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.

Answer 10

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.

Answer 11

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.

Answer 12

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!

Answer 13

Japt, 33 42 bytes

s2
ã fêS üÊo
Vc@ðXãjXVÎlîòZÊ/2Ãd_Ê©ZÎ¥Zo

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 : 
  Ê©          - exists and..
    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.

Answer 14

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.