• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

Is there a formula to figure this out?

F

FM2n

Senior member

My math teacher proposed a number game where you would chop the first number, then skip the next number, and repeat over and over again until you are left with the final number remaining.

So say you take an arbitrary number: 12

Form a circle from the number 1 through 12.

1 2 3 4 5 6 7 8 9 10 11 12

So you chop 1, skip 2, chop 3, skip 4, chop 5, skip 6, chop 7, skip 8, chop 9, skip 10, chop 11, skip 12, then back to the front and chop the number you havent chopped yet, and skip, and chop, until you are left with one number.

Based on this algorithm, is there a formula to determine what the final number is each time, regardless of number chosen? I'm too stupid to figure it out.
 
I'm not sure how to express this mathematically, but the remaining number will be twice the difference between n and the largest power of 2 beneath n.
 
Originally posted by: gbuskirk
I'm not sure how to express this mathematically, but the remaining number will be twice the difference between n and the largest power of 2 beneath n.
Click to expand...

:Q
 
Originally posted by: gbuskirk
I'm not sure how to express this mathematically, but the remaining number will be twice the difference between n and the largest power of 2 beneath n.
Click to expand...
2*[n-2^(n-1)]? That's not it, so maybe you meant 2*[n-(n/2-1)]? Anyway, I'm still not sure what the question is, so it's difficult to answer... 😱
 
I'm no math wizard, but is it not the number that occupies the highest 2^n position in a given set?

2^1 or 2nd position good for set up to a,b,c - answer=b

2^2 or 4th position good for set size <2^2 but >2^3
chop/skip a,b,c,d,e,f,g yields b,d,f -- chop/skip b,d,f yields d or the 2^2 or 4th position.

2^3 or 8th position for set size <2^3 but >2^4

2^4 or 16th position for set size <2^4 but >2^5

 
You misunderstood my statement. I will restate. The remaining number will be twice the difference between n and the largest power of two that is less than n.

Originally posted by: CycloWizard
Originally posted by: gbuskirk
I'm not sure how to express this mathematically, but the remaining number will be twice the difference between n and the largest power of 2 beneath n.
Click to expand...
2*[n-2^(n-1)]? That's not it, so maybe you meant 2*[n-(n/2-1)]? Anyway, I'm still not sure what the question is, so it's difficult to answer... 😱
Click to expand...

 
Given 1-10, strike 1,3,5,7,9 and skip 10
Wrapping around, strike 2,skip 4, strike 6, skip 8, strike 10 and wrap around..
Skip 4, strike 8
Leaves 4
 
Yes, there is a formula.

I wish I remembered it! It's been a while since I did these problems.
IIRC, these were covered in one of my college courses -
abstract algebra or some such course... I can't recall which course.
The worst thing... if I remembered which course, I'd probably remember the fastest approach to solving these problems.

- it'll give me something to work on during the next little while.
 
I'm almost certain it has something to do with the function mod...
(if anyone else is trying to re-discover the formula without looking it up)
 
Originally posted by: sao123
Originally posted by: FM2n
I just tried 10, and my final number was 4...
Click to expand...

should have been 8
Click to expand...

I think he got 4 thinking that you always chop the first number in the list when you loop back around. The wording in the OP makes it sound like that...
 
Originally posted by: jman19
Originally posted by: sao123
Originally posted by: FM2n
I just tried 10, and my final number was 4...
Click to expand...

should have been 8
Click to expand...

I think he got 4 thinking that you always chop the first number in the list when you loop back around. The wording in the OP makes it sound like that...
Click to expand...

I thought that what he meant was that you continued skipping, sort of like playing duck duck goose or something, without regard to the number.
So, if I kept walking around in circles, I'd pass

1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10
If you walk around, first you chop 1,3,5,7,9, then as you continue walking...
you pass 10 and chop the next unchopped number which would be #2 then skip the next unchopped number(which would be 4), then chop the next unchopped number (6), without regard to having completed the circle.

Had it been 1-9, you'd chop the 9, then skip 2, chop 4, skip 6, chop 8,... skip uhhh, 2, chop 6, and 2 is the last number left.

If that's not what the OP meant, then the solution would have been rather easy.
 
Originally posted by: DrPizza
Originally posted by: jman19
Originally posted by: sao123
Originally posted by: FM2n
I just tried 10, and my final number was 4...
Click to expand...

should have been 8
Click to expand...

I think he got 4 thinking that you always chop the first number in the list when you loop back around. The wording in the OP makes it sound like that...
Click to expand...

I thought that what he meant was that you continued skipping, sort of like playing duck duck goose or something, without regard to the number.
So, if I kept walking around in circles, I'd pass

1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10
If you walk around, first you chop 1,3,5,7,9, then as you continue walking...
you pass 10 and chop the next unchopped number which would be #2 then skip the next unchopped number(which would be 4), then chop the next unchopped number (6), without regard to having completed the circle.

Had it been 1-9, you'd chop the 9, then skip 2, chop 4, skip 6, chop 8,... skip uhhh, 2, chop 6, and 2 is the last number left.

If that's not what the OP meant, then the solution would have been rather easy.
Click to expand...

Oh, I'm not saying the OP meant what FM2n thought, just that he probably thought you always chop the first number. I agree that the list should be thought of as a circle where you always just chop every other number.
 
Originally posted by: jman19
Originally posted by: DrPizza
Originally posted by: jman19
Originally posted by: sao123
Originally posted by: FM2n
I just tried 10, and my final number was 4...
Click to expand...

should have been 8
Click to expand...

I think he got 4 thinking that you always chop the first number in the list when you loop back around. The wording in the OP makes it sound like that...
Click to expand...

I thought that what he meant was that you continued skipping, sort of like playing duck duck goose or something, without regard to the number.
So, if I kept walking around in circles, I'd pass

1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10
If you walk around, first you chop 1,3,5,7,9, then as you continue walking...
you pass 10 and chop the next unchopped number which would be #2 then skip the next unchopped number(which would be 4), then chop the next unchopped number (6), without regard to having completed the circle.

Had it been 1-9, you'd chop the 9, then skip 2, chop 4, skip 6, chop 8,... skip uhhh, 2, chop 6, and 2 is the last number left.

If that's not what the OP meant, then the solution would have been rather easy.
Click to expand...

Oh, I'm not saying the OP meant what FM2n thought, just that he probably thought you always chop the first number. I agree that the list should be thought of as a circle where you always just chop every other number.
Click to expand...


Ah yes, thats what I forgot to mention.. If done as a circle, it makes life easier. Chop the first one, skip the next one, etc until there is only one number left off.
 
You can also think of a queue of numbers; the "chopped" ones are discarded and the "skipped" ones are sent to the back of the line. You could simulate this in perl quite easily.

BTW, I stand by the succinct english-language formula given in my first note in this thread, but I was hoping someone could help express it in mathematical notation.
 
I just had to google........succent .....
from the post above...LOL
Thanks to... gbuskirk
..............................................................

Word of the Day for Friday November 3, 2000
succinct \suk-SINGKT\, adjective:
Characterized by compressed precise expression with no wasted words; brief; concise
 
Arrrghhh! No one posted the solution yet. I actually spent about 5 minutes working on it on a napkin last night. It's irritating to see something so simple yet fail to grasp the solution immediately. Perhaps I need to make a list, starting with a circle of 2 up to the 3 or 4 circles I've bothered with, and the solution will jump out at me.
 
The answer is what gbuskirk said; I'll try to rephrase a little better.

For some number n, the answer is 2[n-(2^x)], making 2^x as large as possible while being less than (but NOT equal to) n.

i.e., n=16: 2[16-(2^3)] = 2*(16-8) = 16, which is the right answer.

Basically starting from n=1 and increasing, the answers are as follows:

2,2,4,2,4,6,8,2,4,6,8,10,12,14,16,...

The answers are all multiples of 2 and they keep increasing until they reach the next power of 2, and then they start over.
2^0 terms => repeat, 2^1 terms => repeat, 2^2 terms => repeat, and so on.

I hope I explained this in a better way.
 
Thanks 🙂
I completely missed gbuskirk's post... I just skimmed the thread looking for a formula. I finally spent a couple minutes working out the first few circles and had that "ohh, duhh" moment when I realized I should have just done that in the first place. I came here to post my solution and see it was posted before and now again. Thanks, ninex (and gubskirk)
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top