Two identical strings
- Task
Find and display (here on this page) positive integers whose base 2 representation is the concatenation of two identical binary strings,
where n (in base ten) < 1,00010 (one thousand).
For each decimal number, show its decimal form and also its binary form.
C
<lang c>#include <stdio.h>
- include <stdint.h>
uint8_t bit_length(uint32_t n) {
uint8_t r; for (r=0; n; r++) n >>= 1; return r;
}
uint32_t concat_bits(uint32_t n) {
return (n << bit_length(n)) | n;
}
char *bits(uint32_t n) {
static char buf[33]; char *ptr = &buf[33]; *--ptr = 0; do { *--ptr = '0' + (n & 1); } while (n >>= 1); return ptr;
}
int main() {
uint32_t n, r; for (n=1; (r = concat_bits(n)) < 1000; n++) { printf("%d: %s\n", r, bits(r)); } return 0;
}</lang>
- Output:
3: 11 10: 1010 15: 1111 36: 100100 45: 101101 54: 110110 63: 111111 136: 10001000 153: 10011001 170: 10101010 187: 10111011 204: 11001100 221: 11011101 238: 11101110 255: 11111111 528: 1000010000 561: 1000110001 594: 1001010010 627: 1001110011 660: 1010010100 693: 1010110101 726: 1011010110 759: 1011110111 792: 1100011000 825: 1100111001 858: 1101011010 891: 1101111011 924: 1110011100 957: 1110111101 990: 1111011110
C++
<lang cpp>#include <iostream>
- include <string>
// Given the base 2 representation of a number n, transform it into the base 2 // representation of n + 1. void base2_increment(std::string& s) {
size_t z = s.rfind('0'); if (z != std::string::npos) { s[z] = '1'; size_t count = s.size() - (z + 1); s.replace(z + 1, count, count, '0'); } else { s.assign(s.size() + 1, '0'); s[0] = '1'; }
}
int main() {
std::cout << "Decimal\tBinary\n"; std::string s("1"); for (unsigned int n = 1; ; ++n) { unsigned int i = n + (n << s.size()); if (i >= 1000) break; std::cout << i << '\t' << s << s << '\n'; base2_increment(s); }
}</lang>
- Output:
Decimal Binary 3 11 10 1010 15 1111 36 100100 45 101101 54 110110 63 111111 136 10001000 153 10011001 170 10101010 187 10111011 204 11001100 221 11011101 238 11101110 255 11111111 528 1000010000 561 1000110001 594 1001010010 627 1001110011 660 1010010100 693 1010110101 726 1011010110 759 1011110111 792 1100011000 825 1100111001 858 1101011010 891 1101111011 924 1110011100 957 1110111101 990 1111011110
Cowgol
<lang cowgol>include "cowgol.coh";
sub bitLength(n: uint32): (l: uint8) is
l := 0; while n != 0 loop n := n >> 1; l := l + 1; end loop;
end sub;
sub concatBits(n: uint32): (r: uint32) is
r := (n << bitLength(n)) | n;
end sub;
sub printBits(n: uint32) is
var buf: uint8[33]; var ptr := &buf[32]; [ptr] := 0; loop ptr := @prev ptr; [ptr] := '0' + (n as uint8 & 1); n := n >> 1; if n == 0 then break; end if; end loop; print(ptr);
end sub;
var n: uint32 := 1; loop
var r := concatBits(n); if r > 1000 then break; end if; print_i32(r); print(": "); printBits(r); print_nl(); n := n + 1;
end loop;</lang>
- Output:
3: 11 10: 1010 15: 1111 36: 100100 45: 101101 54: 110110 63: 111111 136: 10001000 153: 10011001 170: 10101010 187: 10111011 204: 11001100 221: 11011101 238: 11101110 255: 11111111 528: 1000010000 561: 1000110001 594: 1001010010 627: 1001110011 660: 1010010100 693: 1010110101 726: 1011010110 759: 1011110111 792: 1100011000 825: 1100111001 858: 1101011010 891: 1101111011 924: 1110011100 957: 1110111101 990: 1111011110
Factor
<lang factor>USING: formatting kernel lists lists.lazy math math.parser sequences ;
1 lfrom [ >bin dup append bin> ] lmap-lazy [ 1000 < ] lwhile [ dup "%d %b\n" printf ] leach</lang>
- Output:
3 11 10 1010 15 1111 36 100100 45 101101 54 110110 63 111111 136 10001000 153 10011001 170 10101010 187 10111011 204 11001100 221 11011101 238 11101110 255 11111111 528 1000010000 561 1000110001 594 1001010010 627 1001110011 660 1010010100 693 1010110101 726 1011010110 759 1011110111 792 1100011000 825 1100111001 858 1101011010 891 1101111011 924 1110011100 957 1110111101 990 1111011110
FreeBASIC
<lang freebasic>dim as uinteger n=1, k=0 do
k = n + 2*n*2^int(log(n)/log(2)) if k<1000 then print k, bin(k) else end n=n+1
loop</lang>
- Output:
3 11 10 1010 15 1111 36 100100 45 101101 54 110110 63 111111 136 10001000 153 10011001 170 10101010 187 10111011 204 11001100 221 11011101 238 11101110 255 11111111 528 1000010000 561 1000110001 594 1001010010 627 1001110011 660 1010010100 693 1010110101 726 1011010110 759 1011110111 792 1100011000 825 1100111001 858 1101011010 891 1101111011 924 1110011100 957 1110111101 990 1111011110
Phix
integer n = 1 sequence res = {} while true do string binary = sprintf("%b%b",n) integer decimal = to_number(binary,0,2) if decimal>1000 then exit end if res &= {sprintf("%-4d %-10s",{decimal,binary})} n += 1 end while printf(1,"Found %d numbers:\n%s\n",{n-1,join_by(res,5,6)})
- Output:
Found 30 numbers: 3 11 54 110110 187 10111011 528 1000010000 693 1010110101 858 1101011010 10 1010 63 111111 204 11001100 561 1000110001 726 1011010110 891 1101111011 15 1111 136 10001000 221 11011101 594 1001010010 759 1011110111 924 1110011100 36 100100 153 10011001 238 11101110 627 1001110011 792 1100011000 957 1110111101 45 101101 170 10101010 255 11111111 660 1010010100 825 1100111001 990 1111011110
Raku
<lang perl6>my @cat = (1..*).map: { :2([~] .base(2) xx 2) }; say "{+$_} matching numbers\n{.batch(5)».map({$_ ~ .base(2).fmt('(%s)')})».fmt('%15s').join: "\n"}\n"
given @cat[^(@cat.first: * > 1000, :k)];</lang>
- Output:
30 matching numbers 3(11) 10(1010) 15(1111) 36(100100) 45(101101) 54(110110) 63(111111) 136(10001000) 153(10011001) 170(10101010) 187(10111011) 204(11001100) 221(11011101) 238(11101110) 255(11111111) 528(1000010000) 561(1000110001) 594(1001010010) 627(1001110011) 660(1010010100) 693(1010110101) 726(1011010110) 759(1011110111) 792(1100011000) 825(1100111001) 858(1101011010) 891(1101111011) 924(1110011100) 957(1110111101) 990(1111011110)
REXX
<lang rexx>/*REXX program finds/displays decimal numbers whose binary version is a doubled literal.*/ numeric digits 100 /*ensure hangling of larger integers. */ parse arg hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 1000 /* " " " " " " */ if cols== | cols=="," then cols= 4 /* " " " " " " */ w= 20 /*width of a number in any column. */
@dnbn= ' decimal integers whose binary version is a doubled binary literal, N < ' , commas(hi)
if cols>0 then say ' index │'center(@dnbn, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─')
- = 0; idx= 1 /*initialize # of integers and index. */
$= /*a list of nice primes (so far). */
do j=1 for hi-1; b= x2b( d2x(j) ) + 0 /*find binary values that can be split.*/ L= length(b); h= L % 2 /*obtain length of the binary value. */ if L//2 then iterate /*Can binary version be split? No, skip*/ if left(b, h)\==right(b, h) then iterate /*Left half match right half? " " */ #= # + 1 /*bump the number of integers found. */ if cols==0 then iterate /*Build the list (to be shown later)? */ c= commas(j) || '(' || b")" /*maybe add commas, add binary version.*/ $= $ right(c, max(w, length(c) ) ) /*add a nice prime ──► list, allow big#*/ if #//cols\==0 then iterate /*have we populated a line of output? */ say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */ idx= idx + cols /*bump the index count for the output*/ end /*j*/
if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ say say 'Found ' commas(#) @dnbn exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?</lang>
- output when using the default inputs:
index │ decimal integers whose binary version is a doubled binary literal, N < 1,000 ───────┼───────────────────────────────────────────────────────────────────────────────────── 1 │ 3(11) 10(1010) 15(1111) 36(100100) 5 │ 45(101101) 54(110110) 63(111111) 136(10001000) 9 │ 153(10011001) 170(10101010) 187(10111011) 204(11001100) 13 │ 221(11011101) 238(11101110) 255(11111111) 528(1000010000) 17 │ 561(1000110001) 594(1001010010) 627(1001110011) 660(1010010100) 21 │ 693(1010110101) 726(1011010110) 759(1011110111) 792(1100011000) 25 │ 825(1100111001) 858(1101011010) 891(1101111011) 924(1110011100) 29 │ 957(1110111101) 990(1111011110) Found 30 decimal integers whose binary version is a doubled binary literal, N < 1,000
Ring
<lang ring>load "stdlib.ring"
decList = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] baseList = ["0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"]
see "working..." + nl see "Numbers whose base 2 representation is the juxtaposition of two identical strings:" + nl
row = 0 limit1 = 1000
for n = 1 to limit1
bin = decimaltobase(n,2) ln = len(bin) if ln & 1 = 0 if left(bin,ln/2) = right(bin,ln/2) row++ see sfl(n, 3) + " (" + sfrs(bin, 10) + ") " if row % 5 = 0 see nl ok ok ok
next
? nl + "Found " + row + " numbers whose base 2 representation is the juxtaposition of two identical strings" ? "done..."
func decimaltobase(nr,base)
binList = [] binary = 0 remainder = 1 while(nr != 0) remainder = nr % base ind = find(decList,remainder) rem = baseList[ind] add(binList,rem) nr = floor(nr/base) end binlist = reverse(binList) binList = list2str(binList) binList = substr(binList,nl,"") return binList
- a very plain string formatter, intended to even up columnar outputs
def sfrs x, y
l = len(x) x += " " if l > y y = l ok return substr(x, 1, y)
- a very plain string formatter, intended to even up columnar outputs
def sfl x, y
s = string(x) l = len(s) if l > y y = l ok return substr(" ", 11 - y + l) + s</lang>
- Output:
working... Numbers whose base 2 representation is the juxtaposition of two identical strings: 3 (11 ) 10 (1010 ) 15 (1111 ) 36 (100100 ) 45 (101101 ) 54 (110110 ) 63 (111111 ) 136 (10001000 ) 153 (10011001 ) 170 (10101010 ) 187 (10111011 ) 204 (11001100 ) 221 (11011101 ) 238 (11101110 ) 255 (11111111 ) 528 (1000010000) 561 (1000110001) 594 (1001010010) 627 (1001110011) 660 (1010010100) 693 (1010110101) 726 (1011010110) 759 (1011110111) 792 (1100011000) 825 (1100111001) 858 (1101011010) 891 (1101111011) 924 (1110011100) 957 (1110111101) 990 (1111011110) Found 30 numbers whose base 2 representation is the juxtaposition of two identical strings done...