Programming exercise/enigma... 4's and 0's

rm_-rf_windows · 09-28-2007, 08:00 PM

I've figured out the algorithm to produce the following output:
4
44
444
4444
44444
444444
etc.

Easy a=a*10 then a=a+4 (the whole thing in a loop).

I can't figure out how to get the following output using a very simple algorithm (loops, etc.) (and I've been thinking about this for several days!):

4
40
44
400
404
440
444
4000
4004
4040
4044
4400
4404
4440
4444
40000
40004
40040
40044
etc.

I've racked my brain out trying to figure this out. All of these numbers can be divided by 4. Some of them can be divided by 10 or 11 . I've thought of combining several sequences {1, 10, 100, 1000, 10000 and (1, 11, 111, 1111, 11111).

If you replace the 4's by 1's you get this: 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, etc. I even thought of trying to do a simple series in binary notation, converting it into strings and then into decimal, then multiplying by four...

I think the easiest solution would be just a few lines of code using 2 or 3 loops, but I just can't figure it out.

BTW, I'm using Pascal, i.e., simple Pascal, not TURBO Pascal.

Many thanks.

osor · 09-28-2007, 08:33 PM

This seems like homework, so I won’t be giving an explicitly coded solution.

Quote:

Originally Posted by rm_-rf_windows

If you replace the 4's by 1's you get this: 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, etc. I even thought of trying to do a simple series in binary notation, converting it into strings and then into decimal, then multiplying by four...

That’s one way to think about it. It should also be pretty easy to code.

Here’s another (mathematically equivalent, yet recursively defined) perspective: suppose a_k is the k-th entry in your sequence (with k=1 denoting the first entry “4”). Also, for this to be elegant, think of a pretend element a_0 = 0 (i.e., when k=0, a_k=0). For all k>1, let j be the actual exponent of the greatest power of two no greater than k (if k is a power of two, then let j=2^k). E.g, when k=35, j=5. Then a recursive formula for a_k is:
a_k = 4*10^(j-1) + a_(k-2^j).

A suitable implementation is left to the reader (*hint: IIRC, Pascal allows recursive functions*).

95se · 09-28-2007, 11:28 PM

Quote:

Originally Posted by rm_-rf_windows

I even thought of trying to do a simple series in binary notation, converting it into strings and then into decimal, then multiplying by four...

Why not just use that? I don't want to give you the answer, but it can be done iteratively or recursively. Either way, it is fairly simple.

rm_-rf_windows · 09-29-2007, 01:08 AM

Many thanks... Thanks too for not having given me the answer. It's not a real (graded) assignment. I think the teacher gave it to us to get us thinking, to amuse us as well, however, it's good that you didn't give me the code... Good practice!

It may not sound that hard to you two, but I haven't done maths in over 20 years! ... Thanks for the clues... I'm going to try and use them to find a solution, then I'll post back. I get the impression osor's post is almost a recipe but that he left some important information out to get me thinking...

Many thanks.

rm_-rf_windows · 09-29-2007, 10:01 AM

Many thanks osor and 95se for your comments, hints, clues and suggestions...

Firstly, in response to 95se's post:

Quote:

Originally Posted by rm_-rf_windows View Post
I even thought of trying to do a simple series in binary notation, converting it into strings and then into decimal, then multiplying by four...

Why not just use that? I don't want to give you the answer, but it can be done iteratively or recursively. Either way, it is fairly simple.

Yeah, okay. I think I can easily figure out how to do the conversions, but I'm not sure how to do binary calculation in Pascal. There must be classic code to create a binary calculator (addition), however, that would be a whole new exercise, perhaps more difficult than the actual problem. Could one of you (or someone) give me the lines of code for this?

The rest of this post is in response to osor's reply:

Quote:

This seems like homework, so I won’t be giving an explicitly coded solution.

It isn't really homework, so feel free to be more explicit (haha)...

Quote:

Here’s another (mathematically equivalent, yet recursively defined) perspective: suppose a_k is the k-th entry in your sequence (with k=1 denoting the first entry “4”). Also, for this to be elegant, think of a pretend element a_0 = 0 (i.e., when k=0, a_k=0). For all k>1, let j be the next smallest power of two (if k is a power of two, then let j=k). E.g, when k=35, j=32. Then a recursive formula for a_k is:
a_k = 4*10^(j-1) + a_(k-j).

Okay, let's break this down into simple steps... Keep in mind that just translating an algorithm into code is already quite difficult for me at this stage of the game, that is, even if the algorithm is already spelled out. What follows below is surely my erroneous interpretation of the information you've given me, although, for pedagogical purposes, I have written down my "thinking aloud". Here goes, one step at a time...

a)

Quote:

suppose a_k is the k-th entry in your sequence (with k=1 denoting the first entry “4”). Also, for this to be elegant, think of a pretend element a_0 = 0 (i.e., when k=0, a_k=0).

Okay, so 0th entry is 0, 1st entry is 4 (intuition tells me that the 2nd entry would be 8, although this is not necessarily true. I think intuition is not a good thing to rely on when solving such problems... But then again Einstein said that intution was very important... Okay, enough of my rambling on about this... and I'm no Einstein either, that's for sure...)
b)

Quote:

For all k>1, let j be the next smallest power of two (if k is a power of two, then let j=k). E.g, when k=35, j=32.

Okay, so the "k>1" bit will omit the zero, but that's a trivial detail...
So when k = { (0), 4, 8, 12, 16, 20... } and j = { ( ), 4, 8, 8, 16, 16, 16, 16, 32, 32, 32, 32, 32, 32, 32, 32, 64... etc.} ... (I think my k sequence is wrong)...

c)

Quote:

E.g, when k=35, j=32.

I guess my k sequence is wrong... Mine doesn't have a 35! Or perhaps this is an arbitrary example?

d)

Quote:

Then a recursive formula for a_k is: a_k = 4*10^(j-1) + a_(k-j).

Just a simple question, "^" here means "to the power of" and NOT "AND". Is that right?

I can see that the number of repetitions of "j" corresponds to the changes in the number of digits in the final output... We could change j to be equal to the exponential value (the actual exponent) corresponding to the above j = { 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6... etc.} I can then understand the beginning of the recursive formula, however, wouldn't it be a_k=4*10^(j-2)...?

As for the last part of the formula, I get the impression that it works at the beginning, but then gives you 404, 408, etc... (again, I tried everything, and when in doubt, I used my intuition to interpret the results).

I need some more details... Once again, I haven't done maths for over 20 years... but it's coming back, slowly but surely... "Chi va piano va sano e lontano" (Italian proverb).

Many thanks.

rm_-rf_windows · 09-29-2007, 10:04 AM

95se,

BTW, Windsor, Ontario, eh? I've been there! How's Windsor these days? What do you do in Windsor (if you don't mind me asking)? Are there software companies in the area or any other computer-related companies?

osor · 09-29-2007, 01:07 PM

Quote:

Originally Posted by rm_-rf_windows

Yeah, okay. I think I can easily figure out how to do the conversions, but I'm not sure how to do binary calculation in Pascal. There must be classic code to create a binary calculator (addition), however, that would be a whole new exercise, perhaps more difficult than the actual problem. Could one of you (or someone) give me the lines of code for this?

So you are counting in binary, the only difference is you use the symbol “4” instead of the symbol “1”. This is much easier than creating a sequence that exhibits your behavior (in the mathematical sense, your sequence is just a_k = k, but the hard part is representing k as a binary number with “4” instead of “1”).

You know how to count in Pascal (use a for loop). All you need now is a function that takes an integer and outputs a string in binary. You can use modulus to find if a number is even or odd. If it’s odd, write a “4”. If not, write a “0”. Then divide by two to get

Code:

var
	k: Integer;

procedure PrintBinary(j:Integer);
begin
	while j > 0 do
	begin
		if (j mod 2) = 0 then
			Write('0')
		else
			Write('4');
		j := j div 2;
	end;
	Writeln('')
end;

begin
	for k := 1 to 20 do
	PrintBinary(k);
end.

The problem with the above code is that the lines need to be reversed (i.e., the most significant bit should be on the left, not the right).

So the output of the code as-is is:

Code:

$ ./sequence
4
04
44
004
404
044
444
0004
4004
0404
4404
0044
4044
0444
4444
00004
40004
04004
44004
00404

But it should be this

Code:

$ ./sequence | rev
4
40
44
400
404
440
444
4000
4004
4040
4044
4400
4404
4440
4444
40000
40004
40040
40044
40400

Of course, it is left as an exercise for the reader to implement line-reversing in the program itself.

osor · 09-29-2007, 01:07 PM

Quote:

Originally Posted by rm_-rf_windows

Okay, let's break this down into simple steps... Keep in mind that just translating an algorithm into code is already quite difficult for me at this stage of the game, that is, even if the algorithm is already spelled out. What follows below is surely my erroneous interpretation of the information you've given me, although, for pedagogical purposes, I have written down my "thinking aloud". Here goes, one step at a time...

Well, the first step is, how is this implemented. Basically, in my method, it ends up being a function, which is called from a loop. E.g.,

Code:

var
	k: Integer;

…

begin
	for k := 1 to 20 do
	Writeln(a(k));
end.

This way, we define a(k) as our function which will return the k-th entry of our sequence as an integer. We can then write this to the screen. So now our problem is to find a suitable definition for the function a(k).

Quote:

Originally Posted by rm_-rf_windows

a)
Okay, so 0th entry is 0, 1st entry is 4 (intuition tells me that the 2nd entry would be 8, although this is not necessarily true. I think intuition is not a good thing to rely on when solving such problems... But then again Einstein said that intution was very important... Okay, enough of my rambling on about this... and I'm no Einstein either, that's for sure...)

These are the fixed entries in our recursive definition. So we start our function with those values hardcoded:

Code:

function a(k:Integer): Integer;
begin
	if k = 0 then
	begin
		a := 0
		Exit
	end
	else if k = 1 then
	begin
		a := 4
		Exit
	end;
	…
end;

Quote:

Originally Posted by rm_-rf_windows

I can see that the number of repetitions of "j" corresponds to the changes in the number of digits in the final output... We could change j to be equal to the exponential value (the actual exponent) corresponding to the above j = { 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6... etc.} I can then understand the beginning of the recursive formula, however, wouldn't it be a_k=4*10^(j-2)...?

I made a mistake in my original (which has been edited). The local variable j should hold the actual exponent of the greatest power of two no greater than k. The mapping between k and j should be as follows

Code:

k = 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  …
j = 0  1  1  2  2  2  2  3  3   3   3   3   3   3   3   4   4   4   4   4  …

Quote:

Originally Posted by rm_-rf_windows

c)
I guess my k sequence is wrong... Mine doesn't have a 35! Or perhaps this is an arbitrary example?

If you continue from above, you get:

Code:

k = …  31  32  33  34  35  36
j = …   4   5   5   5   5   5

So basically, the easiest thing to do would be to define another function (perhaps name it NextPowerOfTwo). This one takes an integer greater than zero and returns the expoenent of greatest power of two which is no greater than the original integer. Then, in the function a(k), you have a local variable called j which is subsequently assigned NextPowerOfTwo(k).

Quote:

Originally Posted by rm_-rf_windows

d)
Just a simple question, "^" here means "to the power of" and NOT "AND". Is that right?

Yes, that’s what I meant.

Quote:

Originally Posted by rm_-rf_windows

As for the last part of the formula, I get the impression that it works at the beginning, but then gives you 404, 408, etc... (again, I tried everything, and when in doubt, I used my intuition to interpret the results).

Well, the last part has changed from my original post (now, it actually works

. You would want something like this:
a_k = 4*10^(j-1) + a_(k-2^j).

95se · 09-30-2007, 10:25 AM

Quote:

Originally Posted by rm_-rf_windows

95se,

BTW, Windsor, Ontario, eh? I've been there! How's Windsor these days? What do you do in Windsor (if you don't mind me asking)? Are there software companies in the area or any other computer-related companies?

I go to the university here

I like the city a lot, but people tend to bash Windsor. Houses are dirt cheap right now, lol.

rm_-rf_windows · 09-30-2007, 04:45 PM

95se,

Wah Court, Franco's Pizza... Windsor has got great pizza ! Little Italy... and Detroit just across the river with a major symphony orchestra, concerts (Cobo Hall, Joe Louis Arena), the Red Wings, Tigers, Pistons... and lots of other stuff... Yeah, Windsor's okay!

I suppose you're studying computer science. Where are you from, originally? What's the computer science department like? Do they offer anything after a Bachelor's degree? Any career prospectives in Windsor for IT specialists?

95se · 10-01-2007, 11:10 PM

Quote:

Originally Posted by rm_-rf_windows

95se,

Wah Court, Franco's Pizza... Windsor has got great pizza ! Little Italy... and Detroit just across the river with a major symphony orchestra, concerts (Cobo Hall, Joe Louis Arena), the Red Wings, Tigers, Pistons... and lots of other stuff... Yeah, Windsor's okay!

I suppose you're studying computer science. Where are you from, originally? What's the computer science department like? Do they offer anything after a Bachelor's degree? Any career prospectives in Windsor for IT specialists?

Hehe, I love Wah Court. Never went to Franco's, though I pass it every time I go to get groceries. Yeah, I am studying CS (last semester!). Windsor has Master's and PhD programs for CS too. I'm actually applying for grad school, but am hoping to get in at U of T (home for me). So, what's a guy from Europe doing in Windsor?