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.
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]
(]#~1#.E.~&":"#:)2^[:i.2>.@^.]
-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.
Œ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)
=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:
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:
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.
ǎ$o'E¨²c
Can't believe I let 05AB1E win for so long smh. Takes input as a string.
ǎ$o'E¨²c
ǎ$o' # Keep substrings of the input (excluding the input) where:
¨² # All the powers of 2
E c # Contains the substring.
💎
Created with the help of Luminespire.
464 -> [4, 4, 64] - test cases suggest duplicates are needed
\$\endgroup\$
≔¹ηＷ‹ηＩθ«Ｅ⌕ＡθＩηＩη≦⊗η
Try it online! Link is to verbose version of code. Explanation:
≔¹η
Start by checking for embedded 1s.
Ｗ‹ηＩθ«
Repeat until we reach the input number.
Ｅ⌕ＡθＩηＩη
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.
DẆṖ×\S$ƇḌḤ’BȦƲƇ
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?
~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!
~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:
(?!^|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.
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);}
With the input n an integer:
function(n,m=2^{0:log2(n-.1)})m[sapply(m,grepl,n)]
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...
function or scan for input. 2. Your solution gives currently wrong outputs for 32 and 655365536. Attempt it online!
\$\endgroup\$
464 or 655365536. OTOH, 0:log2(n-.1) -> 1:log2(n)-1 for -1 byte.
\$\endgroup\$
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
[ all-subseqs 1 head* [ "0"head? ] reject [ dec> 1 - >bin all-eq? ] filter ]
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.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):''
f!-PsT2g#\1P.:
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
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.
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.
•Fmt{∊⟜(𝔽¨𝕩⊸>⊸/2⋆↕𝕩)⊸/∾↑¨↓𝔽𝕩}
∾↑¨↓𝔽𝕩 substrings of input∊⟜(...)⊸/ keep substrings that are found in the constructed list...
𝕩⊸>⊸/2⋆↕𝕩 powers of 2 less than input𝔽¨ convert each element to string