Quantcast

Maximum PC

It is currently Wed Nov 26, 2014 8:35 am

All times are UTC - 8 hours




Post new topic Reply to topic  [ 30 posts ]  Go to page Previous  1, 2
Author Message
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Mon Aug 16, 2010 1:15 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
mag wrote:
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.

A couple of days ago, I was basically thinking along the same lines. Of course, there really isn't any basis for this assumption. It just happens to be the case that the number of bits set to 1 in 3 and 5 sum to the same value in 15. Although the code below demonstrates that the assumption is wrong (or at least incomplete), I still wanted to discuss some aspects of your proof.

Code:
CL-USER> (defun print-bits (nums)
      (dolist (num nums)
        (format t "~3d: ~b~%" num num)))
PRINT-BITS
CL-USER> (print-bits '(3 5 15))
  3: 11
  5: 101
15: 1111
NIL
CL-USER> (print-bits '(2 4 8))
  2: 10
  4: 100
  8: 1000
NIL
CL-USER> (print-bits '(5 7 35))
  5: 101
  7: 111
35: 100011
NIL
CL-USER>


mag wrote:
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).

OK, so far so good, you're using the standard definitions of odd and even to define the value of x.

mag wrote:
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.

Here is where things get a bit fuzzy. Just to be clear, by 2n15, are you saying that if 2*n*15, right? In the equation 5n=2^x, it appears that you're using the previously defined x (ie n = 2x), right? If that isn't the case, it would be better to use instantiate a value of y here (ie there exists a value y such that...).

It is pretty obvious at this point that you're attempting to setup a contradiction, but I'm not following the line of reasoning. If you were to define a couple of theorems (x implies y or something to that effect), perhaps, it would be easier to follow.

Sorry for being a pain... =)


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Mon Aug 23, 2010 4:28 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
My brain hurts...

Monday AM after a week of vacation in a cabin in the woods? As my wife would say "My brain no worky".


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Tue Aug 24, 2010 6:11 pm 
Team Member Top 50
Team Member Top 50

Joined: Sat Jun 25, 2005 11:04 am
Posts: 1026
Gadget wrote:
mag wrote:
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).

OK, so far so good, you're using the standard definitions of odd and even to define the value of x.

mag wrote:
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.

Here is where things get a bit fuzzy. Just to be clear, by 2n15, are you saying that if 2*n*15, right? In the equation 5n=2^x, it appears that you're using the previously defined x (ie n = 2x), right? If that isn't the case, it would be better to use instantiate a value of y here (ie there exists a value y such that...).

I wasn't using the previous x. I did mean 2*n*15 by 2n15.

After posting this, I realized that my first attempt at a proof was just too flawed to try to fix, so I'm going to try a different approach.

Gadget wrote:
Sorry for being a pain... =)

Not at all, I enjoy feedback.


#3 (Attempt #2):

The basis of this proof is the standard way to convert decimal numbers to binary, i.e. divide the decimal number by 2 until it reaches 0 and take the remainders of the divisions as the digits of the binary number.

Example:
Code:
Step    Decimal    /2 =   Division    Remainder
1         75           /2 =   37           1
2         37           /2 =   18           1
3         18           /2 =   9             0
4         9            /2 =    4            1
5         4            /2 =    2            0
6         2            /2 =    1            0
7         1            /2 =    0            1

Binary number: 1001011

As can be seen from the example, for each step, when the decimal is odd, the remainder is 1, i.e. a 1 bit is produced in the binary number. Whether the decimal is odd or not is determined by the ones digit in the decimal number. So, to prove that all multiples of 15 have at least four 1 bits, I will need to prove that for all multiples of 15, there are at least four steps in the decimal-to-binary conversion process that have an odd decimal.

Every even multiple of 15 is double a lower odd multiple of 15, so if all odd multiples of 15 have at least four 1 bits, all even multiples of 15 will have at least four 1 bits. To start with, I will only consider odd multiples of 15.

The below graph shows the possible progressions of the ones digits, starting with five, since I'm only considering odd multiples of 15 right now. To prove that for all multiples of 15, there are at least four steps in the decimal-to-binary conversion process that have an odd decimal, every path in the graph has to eventually have at least four odd digits.

Image
Some notes about the graph:
- the curved arrows indicate a jump, while the straight ones indicate the next step in the process
- the paths terminate after four odd numbers are reached
- the paths marked in yellow produce a path that does not contain four 1 bits, but they represent numbers that are not multiples of 15
- the path marked in green is the path for the above example (marked in red where it overlaps the yellow path


Assuming that this proof stands up, can the general case be proven: for any positive integer x, all multiples of x will contain at least the number of 1 bits that x contains.

Hopefully Gadget doesn't destroy this proof. :)


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Thu Aug 26, 2010 3:25 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
Give me another day or two Mag. I saw your reply the other night, but I haven't had a chance to sit down and read it just yet.


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Sun Sep 05, 2010 6:13 pm 
Team Member Top 50
Team Member Top 50

Joined: Sat Jun 25, 2005 11:04 am
Posts: 1026
Gadget wrote:
Give me another day or two Mag. I saw your reply the other night, but I haven't had a chance to sit down and read it just yet.

This has been a long couple of days. :wink:


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Sun Sep 05, 2010 7:36 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 follow the setup to the graph and I'm familiar with the decimal to binary conversion algorithm that you've used, but I'm lost when it comes to your graph. For example, what does the transition from 5 to 7 actually mean? When do you take that transition?


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Mon Sep 06, 2010 7:26 am 
Team Member Top 50
Team Member Top 50

Joined: Sat Jun 25, 2005 11:04 am
Posts: 1026
Gadget wrote:
I follow the setup to the graph and I'm familiar with the decimal to binary conversion algorithm that you've used, but I'm lost when it comes to your graph. For example, what does the transition from 5 to 7 actually mean? When do you take that transition?

Each circle represents a step: the ones place of the decimal being divided, as well as the remainder of that division. The transitions (arrows) represent the possibilities for the next step.

Using the example, the 5 would represent 75 and the remainder 1. The 7 represents 37 and the remainder 1. The transition from 5 to 7 represents going from step 1 to 2. The rest of the graph follows in the same manner.

I think this answers your question, but if it doesn't let me know.


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Wed Sep 08, 2010 4:36 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
mag wrote:
Assuming that this proof stands up, can the general case be proven: for any positive integer x, all multiples of x will contain at least the number of 1 bits that x contains.

Besides the degenerate cases involving multiples of 1, counter examples are plentiful:
11: 1011 33: 100001
13: 1101 65: 1000001
19: 10011 513: 1000000001
22: 10110 66: 1000010

Although I believe the proof should hold for unary numbers! =)


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Wed Sep 08, 2010 7:37 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
Alright, I see where you're trying to go with the proof now. The part about starting from 5 makes sense (15 + 30 is always going end with a 5 no matter how many times you add 30 to it). A transition from an odd numbered node to another node indicates a remainder of 1 also makes sense.

Here are a couple of (potential) problems that I see with your proof/graph:
1) How do you determine when a number cannot be a multiple of 15 and know when to mark an edge in yellow?
2) As this is a visual representation of the decimal to binary conversion algorithm, path should terminate at a 0 (or 1 if you're saving space); However, as you've stated in your write up, you terminate several of them early.
3) Can you prove there are only two outgoing edges for each node in the graph? Although I came to the same result separately using a script, there is no obvious reason to believe this should be the case (eg 10/2 = 5, 12/2 = 6, 14/2 = 7).

Let's take the tree that you posted (quite nice BTW), remove the redundant nodes, and turn it into a weighted directed graph (note: I removed the edge weights from my graph to reduce the clutter). Reducing to a maximum-flow problem, there cannot be a multiple of 15 with fewer than four 1 bits set unless the minimum flow through the graph from node 5 to node 0 is less than 4. In other words, we can only pass through three odd nodes total. Since 5 and 1 are required nodes, the path from 5 to 0 can only include one additional odd node. The graph on the left includes all of the possible edges; The graph on the right has the 0-5, 1-5, 7-3 and 9-9 nodes removed as paths with these edges will have a flow > 3.

Image

I think this representation makes it easier to visualize problems with this approach to a proof. Obviously, there are still problems to work out (basically, the same problems). Notice there is a cycle of even nodes adjacent to the 5 and 1 nodes. There is also the 9 node right in the middle of this cycle. This means there are potentially an infinite number of paths with a flow of 2 or 3 (ie 2 bits or 3 bits set). Clearly, you won't be able to enumerate all possible values into a tree (w/o breaking this cycle). Granted, the trip from 5 to 0 doesn't guarantee a value that is a multiple of 15, but I'm not sure how you can determine this in advance. And in both cases, there is nothing providing proof that additional valid edges weren't included in the graph.

If there were a way of encoding the multiple of 3 requirement into the graph, then we could solve using max-flow. As it stands, unless there is some way to break the cycle in the middle, I don't think this method will result in a proof.


Top
  Profile  
 
 Post subject: Re: FizzBuzz -- Version 2.0
PostPosted: Sun Sep 12, 2010 5:14 pm 
Team Member Top 50
Team Member Top 50

Joined: Sat Jun 25, 2005 11:04 am
Posts: 1026
Gadget wrote:
Here are a couple of (potential) problems that I see with your proof/graph:
1) How do you determine when a number cannot be a multiple of 15 and know when to mark an edge in yellow?

I work backwards. Going from a lower level (n_i) to a higher level (n_(i+1)), where n_(i+1) = 2*n_i (n_(i+1) is even) or n_(i+1) = 2*n_i + 1 (n_(i+1) is odd).

Take the yellow path on the right side. It starts out with 0, so the next higher level can be 0 or 1; since 1 is the only one on the path, it must be next. For 1, the next higher level can be 2 or 3; since 2 is the only one on the path, it must be next. This continues on with 2, 4, 8, 17, and ends with 35, which is not a multiple of 15.

Gadget wrote:
2) As this is a visual representation of the decimal to binary conversion algorithm, path should terminate at a 0 (or 1 if you're saving space); However, as you've stated in your write up, you terminate several of them early.

I did that on the paths that have already encountered 4 1 bits to save on space.

Gadget wrote:
3) Can you prove there are only two outgoing edges for each node in the graph? Although I came to the same result separately using a script, there is no obvious reason to believe this should be the case (eg 10/2 = 5, 12/2 = 6, 14/2 = 7).

Yes.

When a number is divided by two, (a) the ones digit is either less than, or (b) greater than or equal to its ones digit. (b) is the result of n_i * 2 producing a rollover, while (a) results from no rollover of n_i * 2.

Example with 6 as the ones digit. A case of (a) is 26 / 2 = 13; 13 * 2 does not produce a rollover. A case of (b) is 16 / 2 = 8; 8 * 2 produces a rollover.

I realize this isn't the greatest explanation, but hopefully it gives you some insight. Additionally, since we are only concerned with the ones digit, there is a finite number of possibilities (a small one at that), so it can be shown by iterating through all the possibilities that there are only two outgoing edges.

Gadget wrote:
Let's take the tree that you posted (quite nice BTW), remove the redundant nodes, and turn it into a weighted directed graph (note: I removed the edge weights from my graph to reduce the clutter). Reducing to a maximum-flow problem, there cannot be a multiple of 15 with fewer than four 1 bits set unless the minimum flow through the graph from node 5 to node 0 is less than 4. In other words, we can only pass through three odd nodes total. Since 5 and 1 are required nodes, the path from 5 to 0 can only include one additional odd node. The graph on the left includes all of the possible edges; The graph on the right has the 0-5, 1-5, 7-3 and 9-9 nodes removed as paths with these edges will have a flow > 3.

Image

Thanks. I started to do something like this originally, but I stuck with the method above, because it was easier for me to visualize it. I'll look into this a little more (brush up on and get more experience with graph theory).

Gadget wrote:
I think this representation makes it easier to visualize problems with this approach to a proof. Obviously, there are still problems to work out (basically, the same problems). Notice there is a cycle of even nodes adjacent to the 5 and 1 nodes. There is also the 9 node right in the middle of this cycle. This means there are potentially an infinite number of paths with a flow of 2 or 3 (ie 2 bits or 3 bits set). Clearly, you won't be able to enumerate all possible values into a tree (w/o breaking this cycle). Granted, the trip from 5 to 0 doesn't guarantee a value that is a multiple of 15, but I'm not sure how you can determine this in advance. And in both cases, there is nothing providing proof that additional valid edges weren't included in the graph.

If there were a way of encoding the multiple of 3 requirement into the graph, then we could solve using max-flow. As it stands, unless there is some way to break the cycle in the middle, I don't think this method will result in a proof.

You're right, there is a cycle, but it must eventually break. I'll try to figure this hole out. I think the way to do it is to show that any number the cycle would produce, is not a multiple of 15.

The start of this method:
The cycle would go, removing any internal loops (a temporary deviation from the main cycle), 5, 2, 6, 8, 4, 2, 6, 8, 4, ..., 2, 6, 8, 4, 2 or 3, 1, 0 (2 starts the cycle and 2 or 3 ends the cylce, as can be seen from the graph). This produces a number with only two 1 bits. Starting at 1, n_(i+1) = 2 * n_i, until the very end (5), where n_(i+1) = 2 * n_i. In other words, it is 1000...00001. Adding internal loops back in produces a binary form of 1000...1...0001 (any more than one internal loop produces four 1 bits). So the goal then becomes showing that any number of the form 100...001 (2^n + 1) and 100...1...001 (2^n*(2*n_i + 1) + 1) is not a multiple of 15.


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

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 3 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

© 2014 Future US, Inc. All rights reserved.