Liberty BASIC Community Forum
« small contest: numbers without '11' in binary »

Welcome Guest. Please Login or Register.
Mar 29th, 2017, 9:38pm


Rules|Home|Help|Search|Recent Posts|Notification


« Previous Topic | Next Topic »
Pages: 1  Notify Send Topic Print
 thread  Author  Topic: small contest: numbers without '11' in binary  (Read 602 times)
tsh73
Moderator
ImageImageImageImageImage


member is offline

Avatar

Anatoly (real name)


PM

Gender: Male
Posts: 1609
xx small contest: numbers without '11' in binary
« Thread started on: Apr 3rd, 2012, 06:41am »

Somehow I have no "new thread" button in contest room - so I'll post it here. Really it's just feels too quiet! wink

So. Today our students had "olimpic" in computing - some 16 problems - so I'll repost one I found interesing (and easy enough wink )
Do not be afraid to disrupt their problem solving - it's already over.

Problem:
Quote:
Some coding algorithm uses sequence of numbers,
whose binary representation does not has subsequent '1'.
So 101 is OK while 110 isn't.
First 6 numbers in the sequence are
0, 1, 2 (=binary 10), 4 (=binary 100), 5 (=binary 101), 8 (=binary 1000)

Determine what 576'th number will be.

Write a LB prgram that will show 576'th number.

(I've got 5290.)
User IP Logged

The existence of bug reports means somebody is using the software and actually cares to report back to you that he is having a problem with it, instead of just deleting it from their hard disk.
(Janusz Marcin Gorycki)
stefanhes
Guru
ImageImageImageImageImage


member is offline

Avatar




Homepage PM


Posts: 723
xx Re: small contest: numbers without '11' in binary
« Reply #1 on: Apr 3rd, 2012, 1:19pm »

Code:
sum=0
for i=1 to 6000
   for m=0 to 12
      mask = 2^m + 2^(m+1)
      if (mask and i) = mask _
      then
        sum=sum+1
        print i, i-sum
        exit for
      end if
   next m
   if i-sum = 576 then print "gotcha=";i : end
next i


 


I found 5376 ...(?)
User IP Logged

http://www.soundofanimals.com
http://sincosin.com
tsh73
Moderator
ImageImageImageImageImage


member is offline

Avatar

Anatoly (real name)


PM

Gender: Male
Posts: 1609
xx Re: small contest: numbers without '11' in binary
« Reply #2 on: Apr 3rd, 2012, 2:50pm »

Code:
I found 5376 ...(?) 

The problem says:
Code:
First 6 numbers in the sequence are
0, 1, 2 

It just starts from zero - your program overshoot by one number ;)

Really interesting idea about masks. As they say, there are more then one way to... ;)
I'll post my solution tomorrow - it's on another computer as of now.
User IP Logged

The existence of bug reports means somebody is using the software and actually cares to report back to you that he is having a problem with it, instead of just deleting it from their hard disk.
(Janusz Marcin Gorycki)
stefanhes
Guru
ImageImageImageImageImage


member is offline

Avatar




Homepage PM


Posts: 723
xx Re: small contest: numbers without '11' in binary
« Reply #3 on: Apr 3rd, 2012, 3:02pm »

Code:
sum=0
for i=0 to 6000
   for m=0 to 12
      mask = 2^m + 2^(m+1)
      if (mask and i) = mask _
      then
        sum=sum+1
        print i, i+1-sum
        exit for
      end if
   next m
   if i+1-sum = 576 then print "gotcha=";i : end
next i
 


You're right. I started with 1 instead of 0.
User IP Logged

http://www.soundofanimals.com
http://sincosin.com
tsh73
Moderator
ImageImageImageImageImage


member is offline

Avatar

Anatoly (real name)


PM

Gender: Male
Posts: 1609
xx Re: small contest: numbers without '11' in binary
« Reply #4 on: Apr 4th, 2012, 12:52am »

my approach
Code:
i = 0
while 1
    n=i

    fail = 0
    dPrev = 0
    d=0
    while n
        dPrev = d
        d=n mod 2
        if d and dPrev then fail=1: exit while
        n=int(n/2)
    wend

    if not(fail) then k=k+1: print k, i
    if k = 576 then end     'ends on  5290
    i=i+1
wend
 
User IP Logged

The existence of bug reports means somebody is using the software and actually cares to report back to you that he is having a problem with it, instead of just deleting it from their hard disk.
(Janusz Marcin Gorycki)
Dan Teel
Guru
ImageImageImageImageImage


member is offline

Avatar




Homepage PM

Gender: Male
Posts: 1116
xx Re: small contest: numbers without '11' in binary
« Reply #5 on: Apr 4th, 2012, 02:09am »

the 'ol string approach
Code:
for i = 1 to 575
    if instr(NumToBin$(j),"11") then i=i-1
    j=j+1
next i

print j;" - ";NumToBin$(j)

function NumToBin$(num)
    while num>0
        if (num and 1)=0 then t$="0" else t$="1"
        NumToBin$=t$+NumToBin$
        num=int(num/2)
    wend
end function
 
« Last Edit: Apr 4th, 2012, 02:10am by Dan Teel » User IP Logged

ZPtr.net
stefanhes
Guru
ImageImageImageImageImage


member is offline

Avatar




Homepage PM


Posts: 723
xx Re: small contest: numbers without '11' in binary
« Reply #6 on: Apr 4th, 2012, 03:32am »

on Apr 4th, 2012, 02:09am, Dan Teel wrote:
the 'ol string approach


There is a syntax error in "the 'ol string approach" wink
« Last Edit: Apr 4th, 2012, 03:33am by stefanhes » User IP Logged

http://www.soundofanimals.com
http://sincosin.com
Dan Teel
Guru
ImageImageImageImageImage


member is offline

Avatar




Homepage PM

Gender: Male
Posts: 1116
xx Re: small contest: numbers without '11' in binary
« Reply #7 on: Apr 4th, 2012, 10:04am »

not on mine, be more specific
User IP Logged

ZPtr.net
Stefan Pendl
Global Moderator
ImageImageImageImageImage


member is offline

Avatar

Computers are like babies, you must teach them what you like them to do ...


Homepage PM

Gender: Male
Posts: 5282
xx Re: small contest: numbers without '11' in binary
« Reply #8 on: Apr 4th, 2012, 11:36am »

on Apr 4th, 2012, 10:04am, Dan Teel wrote:
not on mine, be more specific

He means the quoted text wink
User IP Logged

Stefan

Make sure to read and follow the Forum Guidelines

Liberty BASIC Pro 4.04, Windows 7 Home Premium x64 SP1, AMD Turion X2 RM-70 2GHz, 4GB RAM
Dan Teel
Guru
ImageImageImageImageImage


member is offline

Avatar




Homepage PM

Gender: Male
Posts: 1116
xx Re: small contest: numbers without '11' in binary
« Reply #9 on: Apr 4th, 2012, 11:37am »

funny
User IP Logged

ZPtr.net
stefanhes
Guru
ImageImageImageImageImage


member is offline

Avatar




Homepage PM


Posts: 723
xx Re: small contest: numbers without '11' in binary
« Reply #10 on: Apr 4th, 2012, 12:31pm »

ol'=old, 'ol = LOL wink
« Last Edit: Apr 4th, 2012, 12:33pm by stefanhes » User IP Logged

http://www.soundofanimals.com
http://sincosin.com
GaRPMorE
Senior Member
ImageImageImageImage


member is offline

Avatar

"Not everything that counts can be counted, and not everything that can be counted counts." - Albert Einstein


PM


Posts: 288
xx Re: small contest: numbers without '11' in binary
« Reply #11 on: Apr 6th, 2012, 1:54pm »

I also used a string approach, as well as failing to count 0 as the first success.

I like "The tsh Solution." It ran 60% faster than mine (about 730 ms vs 1730).

Also interesting was his use of WHILE 1-WEND rather than [LOOP]-GOTO [LOOP] (or DO LOOP UNTIL). However, it performed about 6% slower on my machine (733 ms vs 689 ms for an average of 50 trials) than the [LOOP] method.
User IP Logged

from the world according to GaRPMorE
uncleBen
Senior Member
ImageImageImageImage


member is offline

Avatar




PM


Posts: 268
xx Re: small contest: numbers without '11' in binary
« Reply #12 on: Apr 6th, 2012, 4:19pm »

My approach: instead of testing each number, just generate them.

n-digit "11-free" binary numbers begin with "10" followed by each "11-free" binary numbers of n - 2 digit (padded with leading zeros).

For example, 5-digit numbers are:
10 000 (16 + 0)
10 001 (16 + 1)
10 010 (16 + 2)
10 100 (16 + 4)
10 101 (16 + 5)

Code:
limit = 576
dim numbers(limit)
numbers(1) = 0
numbers(2) = 1
numbers(3) = 2
powTwo = 4
lastPower = 2
n = 4
while n <= limit
    i = 1
    while n <= limit and numbers(i) < lastPower
        numbers(n) = powTwo + numbers(i)
        'print n, numbers(n)
        n = n + 1
        i = i + 1
    wend
    powTwo = powTwo * 2
    lastPower = lastPower * 2
wend
print numbers(limit)
 


And another one based on the same observation. There's no need to generate all the numbers, as it is known how many "11-free" numbers up to n digits there are (these are Fibonacci numbers).

Code:
limit = 576
maxPlaces = 40
dim places(maxPlaces)
places(0) = 1
places(1) = 2
for i = 2 to maxPlaces
    'Fibonacci numbers, which determines suitable maxPlaces for limit
    places(i) = places(i - 1) + places(i - 2)
next i

result = 0
while limit > 1
    for i = 0 to maxPlaces
        if places(i) >= limit then
            result = result + 2 ^ (i - 1)
            limit = limit - places(i - 1)
            exit for
        end if
     next
wend

print result

 


Now I challenge anyone to find the 1,000,000th number ;)
« Last Edit: Apr 6th, 2012, 5:05pm by uncleBen » User IP Logged

tsh73
Moderator
ImageImageImageImageImage


member is offline

Avatar

Anatoly (real name)


PM

Gender: Male
Posts: 1609
xx Re: small contest: numbers without '11' in binary
« Reply #13 on: Apr 9th, 2012, 01:56am »

uncleBen,
just want to say "wow".
User IP Logged

The existence of bug reports means somebody is using the software and actually cares to report back to you that he is having a problem with it, instead of just deleting it from their hard disk.
(Janusz Marcin Gorycki)
Pages: 1  Notify Send Topic Print
« Previous Topic | Next Topic »

Rules|Home|Help|Search|Recent Posts|Notification

Donate $6.99 for 50,000 Ad-Free Pageviews!

| |

This forum powered for FREE by Conforums ©
Sign up for your own Free Message Board today!
Terms of Service | Privacy Policy | Conforums Support | Parental Controls