11
\$\begingroup\$

Take as input an integer in any reasonable format.

Then, output all the proper sub-strings of the base-10 digits of that integer that are powers of two, in any reasonable format.

Test cases

10230 -> [1, 2]
13248 -> [32, 1, 2, 4, 8]
333 -> []
331 -> [1]
32 -> [2] # As 32 is not a proper sub-string, since it is the whole string. 
322 -> [32, 2, 2]
106 -> [1]
302 -> [2]
464 -> [4, 4, 64]
655365536 -> [65536, 65536]
\$\endgroup\$
4
  • 3
    \$\begingroup\$ Based on the inputs, I assume substrings with leading zeros should not be counted? \$\endgroup\$ Jun 3 at 0:45
  • \$\begingroup\$ Yup! <filler text> \$\endgroup\$ Jun 3 at 1:38
  • 1
    \$\begingroup\$ Can we take input as a list of digits? \$\endgroup\$ Jun 3 at 2:36
  • \$\begingroup\$ Yup, I would consider that a reasonable format. \$\endgroup\$ Jun 3 at 5:04

17 Answers 17

4
\$\begingroup\$

J, 30 bytes

(]#~1#.E.~&":"#:)2^[:i.2>.@^.]

Try it online!

-4 bytes thanks to Neil's approach of generating all the powers of 2 and finding matches.

  • 2^[:i.2>.@^.] All the powers of 2 less than the input.
  • (1#.E.~&":"#:) Gets a count of the matches for each.
  • ]#~ Uses that as a mask to copy the powers of two. Makes copies of those that occur more than once, and removes those that don't occur at all.
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 10 9 bytes

ŒIKʒ¬Ā*bR

Try it online or verify all test cases.

Explanation:

Π        # Get all substrings of the (implicit) input
 IK       # Remove the input itself
   ʒ      # Filter this list by:
    ¬     #  Push its leading digit (without popping the number)
     Ā    #  Check that it's NOT 0 (0 if 0; 1 otherwise)
      *   #  Multiply that to the number
       b  #  Convert it to binary
        R #  Reverse it
          #  (only 1 is truthy in 05AB1E, including "01","001","0001",etc.)
          # (after which the filtered result is output implicitly)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nice power of 2 test! \$\endgroup\$
    – Neil
    Jun 6 at 16:22
4
\$\begingroup\$

Excel, 136 bytes

=LET(s,ROW(1:1024),r,s-1,t,TRANSPOSE(s),p,""&2^r,m,IF(t+r>LEN(A1),,MID(A1,s,t)),TEXTJOIN(",",,IFERROR(m*1^MATCH(IF(--m=A1,,m),p,0),"")))

Input is in cell A1 and is limited to 308 digits long since 2^1023 = 8.99e+307 and that's the highest value Excel can handle in that series.


It's a fairly long formula but LET() allows us to break it into chunks of variable, value except for the last term which is the output.

  • s,ROW(1:999) creates a vertical array of values 1-1024.
  • r,s-1 offsets that array by 1. This is a wash on bytes vs. using s-1 directly later but it does make the formula look nicer.
  • t,TRANSPOSE(s) creates a horizontal array of values 1-1024.
  • p,""&2^r creates an array of string values from 2^0 to 2^1023. It's important later on that these are strings and not numbers.
  • m,IF(t+r>LEN(A1),,MID(A1,s,t)) creates a triangular array of all the various substrings (and also the entire string but that'll get ignored later). For the input of 13248, that looks like this:
    Top Left Corner of m
    (This is just the top left corner since most of the 1024x1024 table is 0.)

That's all the variables we define. The last term is the output so we'll break that down bit by bit.

TEXTJOIN(",",,IFERROR(m*1^MATCH(IF(--m=A1,,m),p,0),""))
  • IF(--m=A1,,m) let's us ignore the entire input even if it's a power of 2. For instance, 32. I could have required the input be a string and then drop the -- here to convert the string m to a number, but Excel defaults to things that look like numbers being numbers and it's worth 2 bytes (to me) to not require funky inputs.
  • MATCH(IF(--m=A1,,m),p,0) tries to find an exact match for the m value in the powers of 2 array. If it doesn't find a match, this will equal #N/A. This is the part that makes it important for the powers to be strings. If we converted m to numbers and matched those, them string like 02 would resolve to be just 2 so they would match. Something line 102 would return 1,2,2 instead of just 1,2.
  • m*1^MATCH(~) multiplies m by either 1 or #N/A.
  • IFERROR(~,"") converts all the errors to blanks. For the input of 13248, that looks like this:
    Top Left Corner of IfError
  • TEXTJOIN(",",,IFERROR(~)) concatenates all the values with a comma between each term.

The screenshot below shows the formula in B1, the results for all the test cases, and the snippets showing partial results for input 13248 that are also shown above.

Screenshot

\$\endgroup\$
1
  • \$\begingroup\$ Wow, it is quite rare for Excel of all things to nearly beat out Python! Incredible golfing! \$\endgroup\$ Jun 3 at 14:21
3
\$\begingroup\$

Charcoal, 20 bytes

≔¹ηW‹ηIθ«E⌕AθIηIη≦⊗η

Try it online! Link is to verbose version of code. Explanation:

≔¹η

Start by checking for embedded 1s.

W‹ηIθ«

Repeat until we reach the input number.

E⌕AθIηIη

Output each copy of the current power of 2 found in the input. (FindAll finds overlapping matches, otherwise 65536 would only be found once in 655365536.)

≦⊗η

Try the next power of 2.

\$\endgroup\$
3
\$\begingroup\$

Jelly, 15 bytes

DẆṖ×\S$ƇḌḤ’BȦƲƇ

Try it online!

How it works

We use that fact that, if \$x = 2^n\$ for some \$n \in \mathbb N \cup \{0\}\$, then the binary representation of \$2x-1\$ consists of all \$1\$s. Note that the \$2x\$ is to handle \$x = 1\$.

DẆṖ×\S$ƇḌḤ’BȦƲƇ - Main link. Takes n on the left
D               - Digits of n
 Ẇ              - All substrings
  Ṗ             - Remove n
      $Ƈ        - Keep those with no leading zeros:
   ×\           -   Scan by product
     S          -   Resultant sum is zero
        Ḍ       - Cast to digits
             ƲƇ - Keep those that are a power of 2:
         Ḥ      -   Unhalve; Double
          ’     -   Decrement
           B    -   Binary
            Ȧ   -   All are non-zero?
\$\endgroup\$
3
\$\begingroup\$

Vyxal, 17 12 bytes

ǎ$o~¨=⌊⌊'ʀEc

Try it Online!

Times out for really long numbers. Lowkey kinda cursed but that's okay with me.

Explained

ǎ$o~¨=⌊⌊'ʀEc
ǎ$o          # All substrings of the input, with the input removed
   ~         # Keep only those that:
    ¨=       #   are invariant under:
      ⌊       #    conversion to int
       ⌊      # convert those to int
        '    # From those numbers (i.e. all substrings that don't have leading 0s), keep those where
         ʀE  #   the range 0 to that number, vectorised to the power of 2,
           c #   contains that number
\$\endgroup\$
3
  • 1
    \$\begingroup\$ @Steffan 464 -> [4, 4, 64] - test cases suggest duplicates are needed \$\endgroup\$
    – lyxal
    Jun 3 at 1:55
  • \$\begingroup\$ 14 bytes \$\endgroup\$
    – Steffan
    Jun 3 at 2:05
  • 2
    \$\begingroup\$ after seeing the Factor answer, 13 bytes \$\endgroup\$
    – Steffan
    Jun 3 at 2:44
3
\$\begingroup\$

Brachylog, 14 bytes

~s.¬?h¬0&cḃ+1∧

Generator solution; takes the full number through its output parameter and yields a power-of-2 substring through its input parameter. Input and output are both lists of digits. Try it online!

Explanation

~s.¬?h¬0&cḃ+1∧
                The input parameter (implicit)
~s              is a consecutive sublist of
  .             the output parameter
   ¬            which is not the same as
    ?           the input parameter
     h          whose first element
      ¬0        is not zero
        &       And, the input parameter
         c      concatenated together
          ḃ     converted to binary
           +    summed
            1   is 1
             ∧  Break unification of 1 with the output parameter

In other words, find a consecutive sublist of digits that satisfies the following conditions:

  • It is not equal to the full list
  • It does not start with 0
  • When treated as a number and converted to binary, it is a 1 followed by some number of 0s
\$\endgroup\$
3
\$\begingroup\$

Retina 0.8.2, 64 bytes

(?!^|0)
$'¶
%`\B
¶$`
O#^$`
$.&
1A`
.+
$*
G`^((.+)(?=\2$))*.$
%`.

Try it online! Explanation:

(?!^|0)
$'¶
%`\B
¶$`

Generate all of the nontrivial substrings of the input integer that do not begin with 0. (Retina 1 can do this using Lw`[1-9].*.)

O#^$`
$.&
1A`

Delete the longest such substring i.e. the original input. (Retina 1 would use N instead of O#.)

.+
$*

Convert to unary. ($* would be just * in Retina 1.)

G`^((.+)(?=\2$))*.$

Keep only powers of two. This works by matching half of the unary number each time until you get to the last 1 at the end. (Retina 1 matches differently and requires you add the m flag.)

%`.

Convert to decimal.

\$\endgroup\$
3
\$\begingroup\$

C (gcc), 99 96 83 81 bytes

  • -5 thanks to ceilingcat
  • -13 thanks to Juan Ignacio Díaz

Takes each power of 2 less than the input number and compares it to slices of the number.

j,k,m;f(i){for(m=j=1;j<i;j*=2)for(m*=j<m?:10,k=i;k;k/=10)k%m-j||printf("%d ",j);}

Try it online!

\$\endgroup\$
0
3
\$\begingroup\$

R, 124 57 71 58 55 50 bytes

With the input n an integer:

function(n,m=2^{0:log2(n-.1)})m[sapply(m,grepl,n)]

Try it online!

Note: Even though 0:n should work on principle, and thus gain 7 bytes against 0:log(n,2), it produces NA for most values of n...

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Some remarks: 1. Input though variable is unacceptable as per our consensus - you should wrap it up as a function or scan for input. 2. Your solution gives currently wrong outputs for 32 and 655365536. Attempt it online! \$\endgroup\$
    – pajonk
    Jun 7 at 8:21
  • 1
    \$\begingroup\$ This still gives wrong results for 464 or 655365536. OTOH, 0:log2(n-.1) -> 1:log2(n)-1 for -1 byte. \$\endgroup\$
    – pajonk
    Jun 7 at 19:50
  • \$\begingroup\$ @pajonk: Thanks, I had not noticed a power had to be posted as many times as it appeared... \$\endgroup\$ Jun 7 at 20:31
2
\$\begingroup\$

Python 3.10.4 - 119 bytes

a=input()
for b in range(len(a)):
 for c in range(len(a)-b):
  n=int(a[c:c+b+1])
  if(n&(n-1)==0)and n!=0:
   print(n)

You type in the number when the program starts, we then iterate over all the possible substrings of that using this code snippet. Then we finally use this method to check if the given substring is a power of two, and if so, print it.

Note: when entering the number, be careful to not have an extra space on the end, as that will cause an error. Here's an example of me running it (on Arch Linux):

[me@computer ~]$ python golf.py
13248  <-- We enter that number ourself with the keyboard, the rest is automatically outputted
1
2
4
8
32

Note to OP:

In some cases (for example 10230), it outputs a number more than once:

$ python golf.py
10230
1
2
2

I assume that is fine, as it is a power of two, even if listed twice. If it isn't, I can update my answer

\$\endgroup\$
5
  • \$\begingroup\$ It ain't exactly what I had in mind when I wrote the challenge. Clever answer though! \$\endgroup\$ Jun 3 at 1:40
  • \$\begingroup\$ @Pyautogui If you want, I can totally update it to not report something twice. Just want to double-check first \$\endgroup\$
    – cocomac
    Jun 3 at 1:41
  • \$\begingroup\$ I'd prefer it closer aligned with the spec given in the question, but it is fine as it is, esp. if it helps you shave off some bytes! \$\endgroup\$ Jun 3 at 2:23
  • 1
    \$\begingroup\$ 91 bytes \$\endgroup\$
    – Steffan
    Jun 3 at 2:31
  • 2
    \$\begingroup\$ 98 that conforms with the requirements \$\endgroup\$
    – Steffan
    Jun 3 at 2:36
2
\$\begingroup\$

Factor, 79 76 bytes

[ all-subseqs 1 head* [ "0"head? ] reject [ dec> 1 - >bin all-eq? ] filter ]

Attempt This Online!

Takes input as a string. -3 bytes from tip by caird coinheringaahing.

  • all-subseqs Get every contiguous subsequence of the input.
  • 1 head* Remove the last one (which is the same as the input).
  • [ "0"head? ] reject Remove the ones that start with zero.
  • [ ... ] filter Select every subsequence whose...
  • dec> 1 - >bin all-eq? ...predecessor's binary digits are all the same.
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 79 bytes

Returns a space-separated string.

f=(s,n=1)=>n<s?(g=s=>s&&(s.match('^'+n)?n+' ':'')+g(s.slice(1)))(s)+f(s,n*2):''

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Pyth, 14 bytes

f!-PsT2g#\1P.:

Try it online!

Accepts a string as input, and returns a list of strings.

.:      -> All positive-length substrings of the (implicit) input
P       -> Remove the last substring (which is the entire string)
g#\1    -> Filter for substrings which start with "1" or greater
f       -> Filter for elements where...
   PsT  ->  ... its list of prime factors
 !-   2 ->  ... is empty when all 2s are removed
\$\endgroup\$
1
  • \$\begingroup\$ Sure, a string is a fine format! \$\endgroup\$ Jun 3 at 17:37
2
\$\begingroup\$

Python 3.10 - 72 bytes

lambda x:sum(([w:=2**n]*(w<x)*str(x).count(str(w))for n in range(x)),[])

Can probably be golfed further - I initially misunderstood the question as wanting no duplicates (i.e. 322 -> [32, 2]), but I think the structure that lead me to is fine. Also, in principle this will work for any input, but it takes several seconds to run on 13248 and will probably take longer than I care to wait on 655365536.

\$\endgroup\$
2
\$\begingroup\$

JavaScript, 70 bytes

f=(n,i=1)=>n>i?[...[...n.matchAll(`(?=${i})`)].fill(i),...f(n,i+i)]:[]

f=(n,i=1)=>n>i?[...[...n.matchAll(`(?=${i})`)].fill(i),...f(n,i+i)]:[]

console.log(JSON.stringify(f("10230"    ))) // [1, 2]
console.log(JSON.stringify(f("13248"    ))) // [32, 1, 2, 4, 8]
console.log(JSON.stringify(f("333"      ))) // []
console.log(JSON.stringify(f("331"      ))) // [1]
console.log(JSON.stringify(f("32"       ))) // [2]
console.log(JSON.stringify(f("322"      ))) // [32, 2, 2]
console.log(JSON.stringify(f("106"      ))) // [1]
console.log(JSON.stringify(f("302"      ))) // [2]
console.log(JSON.stringify(f("464"      ))) // [4, 4, 64]
console.log(JSON.stringify(f("655365536"))) // [65536, 65536]

Input a string, output array of integers.

\$\endgroup\$
2
\$\begingroup\$

BQN, 29 bytes

•Fmt{∊⟜(𝔽¨𝕩⊸>⊸/2⋆↕𝕩)⊸/∾↑¨↓𝔽𝕩}

Try it here!

Explanation

  • ∾↑¨↓𝔽𝕩 substrings of input
  • ∊⟜(...)⊸/ keep substrings that are found in the constructed list...
    • 𝕩⊸>⊸/2⋆↕𝕩 powers of 2 less than input
    • 𝔽¨ convert each element to string
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.