Quantcast

Maximum PC

It is currently Tue Jul 29, 2014 2:26 pm

All times are UTC - 8 hours




Post new topic Reply to topic  [ 30 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: FizzBuzz -- Version 2.0
PostPosted: Sat Aug 07, 2010 12:40 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
In another thread, CrashTech posted a link to a programming interview problem that exposes the incompetence of many "professional" programmers. This thread posts a slight modification of that problem statement, and will hopefully show how competent all of us can be...


Problem: Interestingly enough, most multiples of 15 (at least for those < 1000) when displayed in binary contain four values of 1. For example, the number 15 expressed in binary is 1111. Here is a table with the first 8 multiples of 15, and as you can see, all of them contain 4 1's.
Code:
  15:             1111
  30:            11110
  45:           101101
  60:           111100
  75:          1001011
  90:          1011010
105:          1101001
120:          1111000


Now clearly, there are a few multiples of 15 that do not contain 4 1's in them. For example, 495 is 111101111 in binary.

Question #1 (EASY): What is the largest multiple of 15 that you can find that does not contain 4 1's in binary? This will be an ongoing search like the search for the largest prime number.

Question #2 (HARD): Can you prove that either (a) there an infinite number of multiples of 15 that do not contain 4 1's or (b) there are a finite number. Major kudos to anyone who can express this as a proof.

Question #3 (????): Are there any multiple of 15 with fewer than 4 1s in them?

To save us some pain, please use something like the following syntax:

#1 -- 495 111101111


Top
  Profile  
 
 Post subject:
PostPosted: Sat Aug 07, 2010 2:56 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Oh, come one... 23 views and nobody has posted anything yet?! WTH!!!


Top
  Profile  
 
 Post subject:
PostPosted: Sat Aug 07, 2010 4:53 pm 
Northwood
Northwood
User avatar

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
Gadget wrote:
Oh, come one... 23 views and nobody has posted anything yet?! WTH!!!


N = N* fp ne fl fi fc fL - but none here


Top
  Profile  
 
 Post subject:
PostPosted: Mon Aug 09, 2010 12:47 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Maybe next week I will have time to tackle this on my vacation :)


Top
  Profile  
 
 Post subject:
PostPosted: Thu Aug 12, 2010 8:16 am 
Team Member Top 100
Team Member Top 100

Joined: Sun Feb 12, 2006 2:52 pm
Posts: 1994
Location: Cryptogram City!
Quote:
Question #1 (EASY): What is the largest multiple of 15 that you can find that does not contain 4 1's in binary? This will be an ongoing search like the search for the largest prime number.

Question #2 (HARD): Can you prove that either (a) there an infinite number of multiples of 15 that do not contain 4 1's or (b) there are a finite number. Major kudos to anyone who can express this as a proof.

Question #3 (????): Are there any multiple of 15 with fewer than 4 1s in them?

To save us some pain, please use something like the following syntax:

#1 -- 495 111101111


#1 -- 4,294,967,280 11111111 11111111 11111111 11110000 (28 bits set)
With good ol' Turbo C, the largest integer I can find with more than 4 bits set

#2 -- No! ;)

#3 -- There are no multiples of 15 less than 4 billion, that have less than four 1 bits in them.

I wrote this C program in Turbo C, but have little experience with bit operations.

Code:
#include <stdio.h>
#include <limits.h>

int main() {
  int i, j, k, got1, cbits[33];
  unsigned long n;
  unsigned long a[33];

  printf("\n\n Sizeof(unsigned long): %d maximum unsigned long is: %lu", sizeof(unsigned long), ULONG_MAX);
  n=2;
  i=1;
  a[i]=i;
  /* build powers of 2 array for bit work */
  while(n < ULONG_MAX && n > 0) {
    a[++i] = n;
    printf("\n n == %lu  i== %d", n, i);
    n *= 2;
  }
  k=0;
  n=15;
  while(n < ULONG_MAX) {
    for(j=0;j<33;j++)         //clear the display array
      cbits[j]=0;

    for(i=1, got1=0;i<33;i++) { //find the bits set to 1
      if(n & a[i]) {
        ++got1;
        cbits[i] = 1;          //and mark the array index representing that bit
      }
    }
    if(got1 < 4) { // or got1== 4)  { //or got1 > 27) {
      printf("\n#%6d: N %8lu has %d 1 bits: ", ++k, n, got1);
      for(j=32;j>0;j--) {
        printf("%d", cbits[j]);
        if((j % 8==1) )
          putchar(' ');
      }
    }
    n+=15;
  }
  printf("\n\n\t\t\t     press enter when ready");
  i = getchar();
  return 0;
}


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Thu Aug 12, 2010 2:29 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24222
Location: Granite Heaven
#2:

Any number x expressed in binary may be doubled by adding a zero to the end of its bit string.

Code:
x = 2, x(bin) = 10
2x = 4, 2x(bin) = 100


For any number which contains 15 as a factor and is doubled, the resulting product will also have 15 as a factor by the associative property of multiplication.

Code:
15 = 15 * 1
30 = 15 * 2
X = 15 * y
2X = 15 * 2y


Therefore, given any number X which is a multiple of 15 and does not have 4 ones in its bit string, that number can be doubled an infinite number of times to produce an infinite series of multiples of 15 which do not have 4 1s in their bit string.

Or,
For any x such that x is a multiple of 15 and does not have 4 ones in its bit string, 2^n * X also does not have 4 ones in its bit string for all n > 0, n = integer.

Since we know that at least one number exists that satisfies x, there are an infinite number of multiples of 15 whose bit string do not contain 4 1s.


Top
  Profile  
 
 Post subject: Re:
PostPosted: Thu Aug 12, 2010 4:47 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Adak! It has been a LONG time. WTH, you're programming in Turbo-C now?! BTW, your submission to problem #1 is valid. ;)

Adak wrote:
#2 -- No! ;)

LMAO... you wimp! =)

Adak wrote:
#3 -- There are no multiples of 15 less than 4 billion, that have less than four 1 bits in them.

I didn't come up with any three 1 bits multiples of 15 either. I had previously ran the code below overnight and it didn't pop out anything, but I didn't have it printing out where it had left off either.

Here is the code that I'm using for the <4 1-bits problem... It appears to be a bit shorter than yours! =P
Code:
(defun fizz-15 (start stop)
      (if (not (= (mod start 15) 0))
          (error "~a is not a multiple-value- of 15!~%" start))
      (loop for n from start to stop by 15 do
       (let ((str (format nil "~b" n)))
         (cond ((< (count #\1 str) 4)
           (format t "~5d: ~b~%" n n))
          ((= (mod n 15000000) 0)
           (format t "checked through ~r~%" n))))))
FIZZ-15
CL-USER> (fizz-15 15 1000000000)
checked through fifteen million
checked through thirty million
...
checked through three hundred and seventy-five million

It looks like there still might be a proof out there with your name on it! =)


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Thu Aug 12, 2010 6:09 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Jipstyle wrote:
#2:

Alright Jipstyle... the tech writer saves the day! =)

Jipstyle wrote:
#2: For any x such that x is a multiple of 15 and does not have 4 ones in its bit string, 2^n * x also does not have 4 ones in its bit string for all n > 0, n = integer.

Not only does it have not have 4 ones, but it is the same bit string with an additional 0 on the right.

If we define a proper bit-string as a bit-string with any 0's to the right of the right-most 1 removed, we create a mapping from the smallest multiple of 15 with this proper bit-string to all of the other bit-strings that are some multiple of 2 larger.

5) Are there an infinite or finite number of proper bit-strings that are a multiple of 15 with four 1 bits set? (proof)

6) What is the largest proper bit-string someone can come up with? (similar to the largest prime)

Actually, this is a much better problem in terms of computation now.


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Thu Aug 12, 2010 6:45 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
I'm going to have to take back the last comment of my previous post now...

Code:
(defun range-15 (stop)
  (let ((lst '()))
    (loop for n from 15 to stop by 15 do
     (push n lst))
    (nreverse lst)))

(defun double-range (start stop &optional (n start) (lst nil))
  (if (< n stop)
      (double-range start stop (* 2 n) (push n lst))
    (nreverse lst)))

(defun fizz-15 (stop)
  (let ((sieve (range-15 stop))
   (bit-strings '()))
    (loop while sieve do    
     (push (first sieve) bit-strings)
     (setf sieve
      (set-difference sieve (double-range (first sieve)
                      (1+ (car (last sieve)))))))
    (nreverse bit-strings)))

CL-USER> (setf strings (fizz-15 1000))
(15 45 75 105 135 165 195 225 255 285 ...)
CL-USER> (let ((prev 15))
      (dolist (str strings)
        (format t "~5d: ~20b   diff: ~a~%" str str (- str prev))
        (setf prev str)))
   15:                 1111   diff: 0
   45:               101101   diff: 30
   75:              1001011   diff: 30
  105:              1101001   diff: 30
  135:             10000111   diff: 30
  165:             10100101   diff: 30
  195:             11000011   diff: 30
  225:             11100001   diff: 30
  255:             11111111   diff: 30
  285:            100011101   diff: 30
  315:            100111011   diff: 30
  345:            101011001   diff: 30
  375:            101110111   diff: 30
  405:            110010101   diff: 30
  435:            110110011   diff: 30
  465:            111010001   diff: 30
  495:            111101111   diff: 30
  525:           1000001101   diff: 30
  555:           1000101011   diff: 30
  585:           1001001001   diff: 30
  615:           1001100111   diff: 30
  645:           1010000101   diff: 30
  675:           1010100011   diff: 30
  705:           1011000001   diff: 30
  735:           1011011111   diff: 30
  765:           1011111101   diff: 30
  795:           1100011011   diff: 30
  825:           1100111001   diff: 30
  855:           1101010111   diff: 30
  885:           1101110101   diff: 30
  915:           1110010011   diff: 30
  945:           1110110001   diff: 30
  975:           1111001111   diff: 30
NIL
CL-USER>


Of course, this is going to make it considerably easier for Jipstyle to write a proof!


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Fri Aug 13, 2010 1:14 am 
Team Member Top 100
Team Member Top 100

Joined: Sun Feb 12, 2006 2:52 pm
Posts: 1994
Location: Cryptogram City!
Quote:
LMAO... you wimp! =)

Y'all have a lot more education than I do. What I do have, is decidedly rusty with a capital 'R'. Especially math! ;)

For smaller programs, I prefer Turbo C to Visual C. Turbo C has special extensions to facilitate bit handling, but I didn't use them. I wanted a more "standard" program.

WHAT is that language you're programming in Gadget? I know you prefer some of the less popular languages.

For a laugh, if you haven't done so already, check out the language "Brainphuck" (with an 'f'), on Wikipedia. It's hard not to roll on the floor in fits of laughter, just looking it over.

"Overnight" runs? :shock: :shock:

I know C has been described as having the language elegance of two tin cans and a piece of string, but it does romp. My code runs are done in 1/2 -5 minutes, depending on how much output I have it set for. Have to comment out the getchar()'s of course.

And my code isn't efficient - it always continues to the end of the a[] array values, even though it can't use them any more. I left it like this because it makes looking at the code, easier.

And I'm lazy! ;)


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Fri Aug 13, 2010 1:33 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Haha... I can't seem to get any sleep tonight either. =)

I wrote a new version looking for the first multiple of 15 with three 1 bits set. Instead of searching multiples of 15, I decided to do something a bit more intelligent. A "proper" bit-string will have both the first and last bits set to 1, therefore you only need to set one more bit to 1 within the bit-string and check to see if the value is a multiple of 15. There is an example in the code below that makes everything very clear.

So far, I've check all bit-strings up to 500 bits in length and didn't find a single match. I'll check through 1000 before stopping the search.

Code:
(defun 3bit-values (num-bits)
      (let ((base (1+ (expt 2 (1- num-bits))))
       (values '()))
        (loop for i from 1 to (- num-bits 2)
         do (push (+ base (expt 2 i)) values))
        (nreverse values)))
3BIT-VALUES
CL-USER> (3bit-values 5)
(19 21 25)
CL-USER> (defun check-for-3bit (start-bits max-bits &optional (prn nil))
      (let ((values '()))
        (loop for num-bits from start-bits to max-bits
         do (setf values (3bit-values num-bits))
         (dolist (value values)
           (if prn (format t "checking: ~:d  bit-string: ~10b~%" value value))
           (if (= (mod value 15) 0)
          (format t "found: ~a~%" value))))))
CHECK-FOR-3BIT
CL-USER> (check-for-3bit 8 9 t)           ;;Checks all possible bit-strings that are 8 and 9 bits long...
checking: 131  bit-string:   10000011
checking: 133  bit-string:   10000101
checking: 137  bit-string:   10001001
checking: 145  bit-string:   10010001
checking: 161  bit-string:   10100001
checking: 193  bit-string:   11000001
checking: 259  bit-string:  100000011
checking: 261  bit-string:  100000101
checking: 265  bit-string:  100001001
checking: 273  bit-string:  100010001
checking: 289  bit-string:  100100001
checking: 321  bit-string:  101000001
checking: 385  bit-string:  110000001


Adak wrote:
WHAT is that language you're programming in Gadget? I know you prefer some of the less popular languages.

That is Common Lisp. IIRC, wasn't an older version of BASIC your language of choice a few years back?

Adak wrote:
For a laugh, if you haven't done so already, check out the language "Brainphuck" (with an 'f'), on Wikipedia. It's hard not to roll on the floor in fits of laughter, just looking it over.

I'm somewhat familiar with the language due to stories from other people, but I haven't tried to do anything with it. Someday I'll do a small program in it. I hear that even a simple program is a very sobering experience.

Adak wrote:
I know C has been described as having the language elegance of two tin cans and a piece of string, but it does romp. My code runs are done in 1/2 -5 minutes, depending on how much output I have it set for. Have to comment out the getchar()'s of course.

I was just letting it run in the interpreter without having compiled the code. See if you can beat this one...

Here, I check all of the candidate 3 1-bit set bit-strings up to 100 bits in length in a tenth of a second. ;)

Code:
CL-USER> (time (check-for-3bit 3 100)) 
Real time: 0.102 sec.
Run time: 0.0780005 sec.
Space: 311584 Bytes
GC: 1, GC time: 0.0312002 sec.
NIL


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Fri Aug 13, 2010 4:29 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Interesting indeed. I will try to work on this over the coming week while on vacation :)

However, in addition to Brainfuck... try this one out: http://lolcode.com/


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Fri Aug 13, 2010 7:07 am 
Team Member Top 100
Team Member Top 100

Joined: Sun Feb 12, 2006 2:52 pm
Posts: 1994
Location: Cryptogram City!
Gadget wrote:
...
A "proper" bit-string will have both the first and last bits set to 1, therefore you only need to set one more bit to 1 within the bit-string and check to see if the value is a multiple of 15.

So far, I've check all bit-strings up to 500 bits in length and didn't find a single match. I'll check through 1000 before stopping the search.

That is Common Lisp. IIRC, wasn't an older version of BASIC your language of choice a few years back?


QuickBasic (which has both an interpreter and a compiler), was my programming "refuge" for a long time. I took a one semester course in C, but then didn't use it for much, and forgot a lot. Thanks to a couple good C books, and some C forums, I've learned quite a bit. C is my language of choice for everything, now.

I have never heard of "proper" bit strings having two bits already set to 1. I was using unsigned long's with 4 bytes each. None of the bits are already set to 1, in my program. "They get their 1 the hard way -- they earn it." ;)

Unclear about the rightmost bit being set to 1 all the time, in your program. Think of 30, etc. The right hand bit is zero in these cases.

Your program romps, but it's doing a different job.:mrgreen: Common Lisp is obviously a very expressive language.

If I understand Jipstyle's post, we won't be finding any multiples of 15 with less than 4 bits set, no matter how far out we search. No instance being found in the first 4 billion numbers, we won't find any multiplies of that number which have less than 4 bits set, either.

Fun exercise though. I'm not used to bit work, so it was challenging.


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Fri Aug 13, 2010 8:37 am 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24222
Location: Granite Heaven
CrashTECH wrote:
Interesting indeed. I will try to work on this over the coming week while on vacation :)


As the pro dev in the group, I think you should handle the new proof.

I might give you to the end of the weekend to solve it .. but I admit that I'm impatient. The last one was too easy. :P


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Fri Aug 13, 2010 8:57 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Jipstyle wrote:
CrashTECH wrote:
Interesting indeed. I will try to work on this over the coming week while on vacation :)


As the pro dev in the group, I think you should handle the new proof.

I might give you to the end of the weekend to solve it .. but I admit that I'm impatient. The last one was too easy. :P


LOL, then you'll end up solving it. I am going to be too busy this weekend.


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Fri Aug 13, 2010 8:58 am 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24222
Location: Granite Heaven
Me too .. but it'll be on my mind. Anything to distract me from the hundreds of feet of air under me. :?


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Fri Aug 13, 2010 11:08 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Update:
I've check all of the "proper", or perhaps reduced is a better term, bit-strings up to 10,000 bits in length. That is probably sufficient evidence for someone to begin a proof of why there are no three 1-bits set bit-strings that are a multiple of 15. If I have time, I'll start on it later today.

Also, there appear to be an infinite number of multiples of 15 that are a "proper or reduced bit-string". Another proof!

Adak wrote:
If I understand Jipstyle's post, we won't be finding any multiples of 15 with less than 4 bits set, no matter how far out we search. No instance being found in the first 4 billion numbers, we won't find any multiplies of that number which have less than 4 bits set, either.

No... darn old guys... I swear! =)
I'll explain the proof that he provided below.

Adak wrote:
I have never heard of "proper" bit strings having two bits already set to 1.
<snip>
Unclear about the rightmost bit being set to 1 all the time, in your program. Think of 30, etc. The right hand bit is zero in these cases.

I created the ad hoc definition of a "proper bit-string" a couple of posts back after thinking about the proof that Jipstyle provided. He showed that if a number is a multiple of 15, lets start with 15 (1111) or 3*5 factored, then we can simply multiple by 2, and so will 30, 60, 120, 240... to infinity, and beyond!

15 - 1111 = 3 * 5
30 - 11110 = 3 * 5 * 2
60 - 111100 = 3 * 5 * 2 * 2
120 - 1111000 = 3 * 5 * 2 * 2 * 2
240 - 11110000 = 3 * 5 * 2 * 2 * 2 * 2

Each is clearly a multiple of 15 due to the prime factors 3 and 5 never being disturbed (multiplying by 2 simply adds a 0 to the right). The notion of a "proper" bit-string came from thinking about this in reverse. If I give you any binary number that is a multiple of 15 and the right-most bit is a 0, we can immediately remove the 0 from the right (ie divide by 2), and we will now have a smaller multiple of 15 (as the prime factors of 3 and 5 are unchanged). Do this until the right-most bit is a 1, and we have what I have been calling a "proper" bit-string (again, perhaps reduced is a better term).

Instead of searching through all multiples of 15 for a number with only three 1-bits set, I've reduced the search space enormously by only searching for a "proper" bit-string. Of course, if I were to find one, then we know that there are an infinite number of multiples of 15 by the proof that Jipstyle provided.

Does that make sense now?


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Fri Aug 13, 2010 10:40 pm 
Team Member Top 100
Team Member Top 100

Joined: Sun Feb 12, 2006 2:52 pm
Posts: 1994
Location: Cryptogram City!
< :idea: >

I gotcha! :mrgreen:

But only 1,500 bits tested? Slacker! <just :wink: kidding>


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Sun Aug 15, 2010 12:25 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Adak wrote:
But only 1,500 bits tested? Slacker! <just :wink: kidding>

1500? Shoot... that WOULD be slacking off. 10,000 bits!


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Sun Aug 15, 2010 11:53 am 
Team Member Top 50
Team Member Top 50

Joined: Sat Jun 25, 2005 11:04 am
Posts: 1026
#3:

Before I begin, I will say there is one assumption I've made: that since 3 and 5 both have two bits, then 3*5 will result in 15 with four bits. Therefore, any modification to 15 that would result in 15 with fewer than four 1s, would result in 3 and/or 5 having one 1. So, in order to prove all multiples of 15 have at least four 1s, I prove that all multiples of 3 and 5 have at least two 1s.

All multiples of 15 can be expressed as 15*x. It can further be broken down as even multiples (where x = 2n) and odd multiples (where x = 2n+1).
even:
2n15 = 2*3*5*n
for an even multiple of 15 to not have four bits, one of the following must be true:
5n=2^x or 3n=2^x, because one of the factors of 15 must have only one bit.

5n=2^x:
For 5 to be a factor of 2^x, 2^x must have a 0 or 5 in the ones column (decimal)

2^x:
Spoiler: show
2
4
8
16
32
64
128


A pattern for the ones column appears: it repeatedly progresses through 2, 4, 8, and 6. Since the ones column can't have a 0 or 5, 5n != 2^x.

3n=2^x:
For 3 to be a factor of 2^x, 3n must have only one 1 in it, so we want to prove that 3n will have 2 or more 1s.

3n:
Spoiler: show
000 011
000 110
001 001
001 100
001 111
010 010
010 101
011 000
011 011
011 110
100 001
100 100
100 111
101 010
101 101
110 000
110 011


Looking at the 3 right furthest bits, a pattern emerges: 011, 110, 001, 100, 111, 010, 101, and 000. The only time that a multiple of 3 can have only one 1, is every 8th multiple. So we need to prove 3*8n will always have two or more 1s.
3*8n = 3*4*2n = 12*2n:
Spoiler: show
Code:
12      0001 100
24      0011 000      2*12
36      0100 100
48      0110 000      2*24
60      0111 100
72      1001 000      2*36
84      1010 100
96      1100 000      2*48


Again, looking at the 3 right furthest bits, a pattern emerges: 100 and 000. For every multiple that has a 000 as its three right most bits, it is two times a previous multiple; since the previous multiple has at least two 1s, the current multiple also has two 1s.

Therefore, 3n != 2^x. Since 3n != 2^x and 5n != 2^x, even multiples of 15 will have at least four 1s.

odd:
(2n+1)15 = (2n+1)3*5, (2n+1)3 = n_1, (2n+1)5 = n_2
For an odd multiple of 15 to not have four bits one of the following must be true:
5n_1=2^x or 3n_2=2^x, because one of the factors of 15 must have only one bit.

Since 5n_1 != 2^x and 3n_2 != 2^x has already been proven above, odd multiples of 15 will have at least four 1s.

Since odd and even multiples of 15 have at least four 1s, all multiples of 15 have at least four 1s.


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 30 posts ]  Go to page 1, 2  Next

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 0 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group