Symmetristen binäärien lukujono

Yhtenä päivänä tuli mieleen tutkia millainen lukujono syntyy symmetrisistä binääreistä. Ideana oli juoksuttaa kokonaislukuja väliltä {1...n} ja testata jokaisen luvun kohdalla onko siitä muodostuva binääriluku palindromi, eli symmetrinen. Lähestyin ongelmaa koodaamalla lyhyen c/c++ koodin (testpali.cpp), jonka tehtävä oli tarkistaa symmetria ja antaa paluuarvo sen perusteella. Lukujen syöttämisen päätin jättää yksinkertaiselle bash-skriptille (pali.sh). Skriptiä askarrellessa huomasin heti, että sitä voi nopeuttaa 50% syöttämällä tarkistimelle vain parittomia lukuja.

Tuloksena syntyi seuraavanlainen lukujono. Esittämällä listan Ilman oikean puoleista selventävää binäärilukua (ts. esittämällä pelkät 10-kantaiset kokonaisluvut) sain muutamat ystäväni ihmettelemään lukujonon muodostumislogiikkaa. Kiintoisa sivuhuomio on, että lukusarjan binääriluvut ovat pituuksittain systemaattisissa nipuissa: 1-1-2-2-4-4-8-8-16-16-32-32-n-n. Kahteen saman mittaiseen symmetriseen binäärilukuun voi myös kohdistaa minkä tahansa Boolen algebran operaation, ja lopputulos on yhä symmetrinen (tosin sillä edellytyksellä, että operaatiossa mahdollisesti syntyviä etunollia ei saa pudottaa pois, eli saman mittaisuuden ehto kohdistuu myös lopputulokseen).

testpali.cpp

#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
    if(argc!=2)
    {
        //Invalid params -> exit
        return -1;
    }

    int len,i,j,flag=1;

    //Calculate length
    for(len=0;argv[1][len]!='\0';++len);

    //Test if binary palindrome
    for(i=0,j=len-1;i<len/2;++i,--j)
    {
        if(argv[1][j]!=argv[1][i])
        flag=0;
    }

    /* return 0; if is palindrome, or 1; if not */
    return flag;
}

pali.sh

#!/bin/sh

x=-1

while [ $x -le 999999 ]
do
  x=$(( $x + 2 ))
  #echo -n "$x "
  echo "obase=2; $x" | bc | xargs ./testpali
  retVal=$?
  if [ $retVal -ne 0 ]; then
    echo -n "$x\t"
    echo "obase=2; $x" | bc
  fi
done