psyang said my series was missing one so I recalculated it. Once again no solution, but a few comments someone might find helpful (or completely misleading!) but I did compute the f(n) for the first 100 values of n
Spoiler!
The values where f(n)=n for the first 100 positive integers are:
I'm more confident in this than I was in my previous hand calculated set as I did it in Excel, which doesn't make computational errors (and I did previously, which is why my last set was missing 21).
If anyone thinks the values of f(n) for the other values of n would be helpful I can post the entire table, but I don't see a use case for those.
The gaps in the pattern are not predictable in an obvious way. I tried to curve fit this data set to a variety of functions and got no useable results. I also tried checking just the results from the different piecewise portions of the function (equations 4/5) and had no useable results there.
The only observation I have that might be of any value is that the set of numbers above only has adjacent odd numbers when the even number between them is a power of 2.
ie
1/3 have 2^1=2 between them
3/5 have 2^2=4 between them
7/9 have 2^3=8 between them
15/17 have 2^4=16 between them
31/33 have 2^5=32 between them
63/65 have 2^6=64 between them
I will run this out to see if that holds.
It does. I went to 150 and you get 107,119,127,129.
so 127/129 have 2^7=128 between them. I doubt that's a coincidence, but it doesn't explain the other values in the set. More thought required for sure.
f(5)=5 and my solution includes that, since 2^2+1=5
However, f(11)=13, so I will have to rethink this.
Spoiler!
I must have misunderstood. I thought you said the only solutions were 1 and values that were 3 mod 4. That's why I said 5 was a counter example since it is 1 mod 4.
psyang said my series was missing one so I recalculated it. Once again no solution, but a few comments someone might find helpful (or completely misleading!) but I did compute the f(n) for the first 100 values of n
Spoiler!
The values where f(n)=n for the first 100 positive integers are:
I'm more confident in this than I was in my previous hand calculated set as I did it in Excel, which doesn't make computational errors (and I did previously, which is why my last set was missing 21).
If anyone thinks the values of f(n) for the other values of n would be helpful I can post the entire table, but I don't see a use case for those.
The gaps in the pattern are not predictable in an obvious way. I tried to curve fit this data set to a variety of functions and got no useable results. I also tried checking just the results from the different piecewise portions of the function (equations 4/5) and had no useable results there.
The only observation I have that might be of any value is that the set of numbers above only has adjacent odd numbers when the even number between them is a power of 2.
ie
1/3 have 2^1=2 between them
3/5 have 2^2=4 between them
7/9 have 2^3=8 between them
15/17 have 2^4=16 between them
31/33 have 2^5=32 between them
63/65 have 2^6=64 between them
I will run this out to see if that holds.
It does. I went to 150 and you get 107,119,127,129.
so 127/129 have 2^7=128 between them. I doubt that's a coincidence, but it doesn't explain the other values in the set. More thought required for sure.
Spoiler!
Really interesting observation. It's a pattern I hadn't noticed, but it makes sense. Keep digging!
Another step that I think has to be relevant and/or a solution, but one that absolutely does not come with a proof.
Spoiler!
So, I calculated the set of f(n)=n above, and I've been trying to find patterns. Fact that +/- 1 of every power of 2 was in the list seemed relevant. I spent some time expressing each one in terms of the nearest powers of 2, when I realized that's basically binary.
The set is 1,3,5,7,9,15,17,21,27,31,33,45,51,63,65...
So while I can't in any way prove it, f(n)=n for the positive integers that are symmetrical when expressed in binary.
Frankly, I'm amazed that such a function exists. If you asked me to do this the other way (find a function where this was true) I absolutely could not do it. (And I did spend some time thinking about whether that was a function, specifically did it have only one value of f(x) for every value of x)
This does fit my previous "no odds" observation, because every symmetrical number in binary ends with a 1, which precludes it from being even.
Anyway, this is past my abilities for an analytical solution. I tried to treat it like a system of equations and got nowhere. Empirical solutions are my specialty - but even I recognize that this is a problem that almost certainly has an elegant analytical solution that I am missing, because there's no way something like that happens as a weird happenstance- someone smarter than me created this problem by back calculating the function somehow.
Thanks for posting this one! I won't be able to make any more progress I dont think but I enjoyed the hunt, and it's not something I would have even believed was possible to create.
The Following User Says Thank You to bizaro86 For This Useful Post:
Another step that I think has to be relevant and/or a solution, but one that absolutely does not come with a proof.
Spoiler!
So, I calculated the set of f(n)=n above, and I've been trying to find patterns. Fact that +/- 1 of every power of 2 was in the list seemed relevant. I spent some time expressing each one in terms of the nearest powers of 2, when I realized that's basically binary.
The set is 1,3,5,7,9,15,17,21,27,31,33,45,51,63,65...
So while I can't in any way prove it, f(n)=n for the positive integers that are symmetrical when expressed in binary.
Frankly, I'm amazed that such a function exists. If you asked me to do this the other way (find a function where this was true) I absolutely could not do it. (And I did spend some time thinking about whether that was a function, specifically did it have only one value of f(x) for every value of x)
This does fit my previous "no odds" observation, because every symmetrical number in binary ends with a 1, which precludes it from being even.
Anyway, this is past my abilities for an analytical solution. I tried to treat it like a system of equations and got nowhere. Empirical solutions are my specialty - but even I recognize that this is a problem that almost certainly has an elegant analytical solution that I am missing, because there's no way something like that happens as a weird happenstance- someone smarter than me created this problem by back calculating the function somehow.
Thanks for posting this one! I won't be able to make any more progress I dont think but I enjoyed the hunt, and it's not something I would have even believed was possible to create.
We have a winner! So glad you kept at it!
Spoiler!
I could tell you were on the right path, but looking at the binary representation of n isn't an obvious step. Finding the values before/after the powers of 2 was a great insight on your part.
I found a different pattern that lead to the discovery of what f actually does. I'll share when the solution to the followup below is found.
So, while you have correctly discovered the conditions on n for which f(n)=n, I'm curious if anyone would like to take a stab at what f actually does to n, and then to prove that that is the case.
Ok, well it's clear that 1 and 2 are satisfied by g since g(1) = 1 and g(3) = 3 (3 is 11 in binary).
For #3, we know that 2n is the same as a bitshift left of the binary representation of n, which is the same as appending a 0 to the end of the binary string. Reversing that would be the same as 0 followed by the reverse of n, or 0 followed by g(n) which is, of course, g(n).
For #4, the left hand side is g(4n+1) which is performing these operations:
1) shift n left twice [4n]
2) add 1 [+1]
3) reverse the bitstring [g()]
which yields 10[reverse of n]
The right hand side performs these operations:
for g(2n+1):
1) shift n left once [2n]
2) add 1 [+1]
3) reverse the bitstring [g()]
which gives 1[reverse of n] or, 2^k + g(n), where k is 1+high bit index of n.
So 2g(2n+1) is
2^k+1 + 2g(n)
4) we then subtract g(n) from the above which gives
2^k+1 + g(n)
=10[reverse of n]
which is the same as the left hand side.
The final relation is done similarly.
LHS performs:
1) shift n left twice [4n]
2) append 11 [+3]
3) reverse [g()]
This yields
11[reverse of n]
RHS performs:
1) shift n once [2n]
2) add 1 [+1]
3) reverse [g()]
This yields 1[reverse of n] or, put another way, 2^k + g(n) where k is 1+high bit index of n.
4) Multiply by 3 and subtract 2g(n) yields
3(2^k + g(n)) - 2g(n)
=3*2^k + g(n)
= 2^k+1 + 2^k + g(n)
= 11[reverse of n]
= LHS.
Does there exist any two distinct integers a and b such that 2^a is just a rearrangement of the digits of 2^b?
A rearrangement of the digits is when the same digits are re-ordered to make a new number: 12345 is a rearrangement of 45321. It is not a rearrangement of 4532 or 453212 or 4532.1 for example.
Does there exist any two distinct integers a and b such that 2^a is just a rearrangement of the digits of 2^b?
A rearrangement of the digits is when the same digits are re-ordered to make a new number: 12345 is a rearrangement of 45321. It is not a rearrangement of 4532 or 453212 or 4532.1 for example.
If yes, provide an example. If no, show why not.
No bites? This one is definitely a bit more in the number theory category.
Hint
Spoiler!
If 2^a and 2^b are rearrangements of their digits, they must have the same number of digits which limits how far apart a and b can be.
It also means they must have the same digits, which may make the mod operator useful.
I had another good number theory type problem, but I'll do that later. People seem to enjoy the more "practical" ones. So try this one.
You have two balls made of some new substance, and you want to determine the highest floor of a 100 storey building from which you can drop a ball and have it not break. Once a ball breaks, it can't be used again.
The brute force method would be to start at the first floor, and keep dropping a ball until it breaks. Then the previous floor would be the answer. This could take up to 100 drops, however (assuming the first floor starts above the main floor).
What's the minimum number of drops you must make to figure this out?
Location: In my office, at the Ministry of Awesome!
Exp:
Quote:
Originally Posted by psyang
I had another good number theory type problem, but I'll do that later. People seem to enjoy the more "practical" ones. So try this one.
You have two balls made of some new substance, and you want to determine the highest floor of a 100 storey building from which you can drop a ball and have it not break. Once a ball breaks, it can't be used again.
The brute force method would be to start at the first floor, and keep dropping a ball until it breaks. Then the previous floor would be the answer. This could take up to 100 drops, however (assuming the first floor starts above the main floor).
What's the minimum number of drops you must make to figure this out?
Comment on your last one
Spoiler!
Technically speaking you didn't prove that Mod9( 2^x) follows a pattern
I don't know the exact notation for Mod notation.
But I believe you.
To the new one
Spoiler!
I can get it as low as 19
Drop on 10, 20, 30 etc till one breaks, then start at 11, 21, 31 ect and drop each floor till it breaks, highest would be 19 drops:
10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 91, 92, 93, 94, 95, 96, 97, 98, 99
Using just straight multiples you get a max number of drops of
Interval = x (ie, if you're going to drop every 3rd floor, the interval (x) = 3
Max Drops for an interval = 100/x (rounded to the nearest whole number) + x-1
so for X = 2
Max Drops = 100/2 + 1 = 51
For x = 10
Max drops = 100/10 + 9 = 19
You get the same number of drops for 11 or 12
X = 11 = 100/11 + 10 = 9+10=19
x = 12 = 100/12 + 11 = 8 + 11 = 19
I can't remember the notation for truncating/rounding
Anyway, it's a minimum at an interval of 10-12
That being said, there is maybe another way to do it, but that's my quick crack at it.
__________________
THE SHANTZ WILL RISE AGAIN. <-----Check the Badge bitches. You want some Awesome, you come to me!
The maximum number of eliminations will always come from cutting the sample in half, way faster than using fixed increment sizes.
So if you pick an edge floor (1) the series would go: 50,25,13,7,4,2,1
So I got 7. I tried a few other numbers and got the same answer, and I don't believe it can be done faster, because if you ever do something that isn't cutting the remainder in half you made your guess have less informational value in the case where it isn't correct.
Edited to add: whoops, I misread the problem as how many balls was the minimum, not how many drops with 2 balls
The maximum number of eliminations will always come from cutting the sample in half, way faster than using fixed increment sizes.
So if you pick an edge floor (1) the series would go: 50,25,13,7,4,2,1
So I got 7. I tried a few other numbers and got the same answer, and I don't believe it can be done faster, because if you ever do something that isn't cutting the remainder in half you made your guess have less informational value in the case where it isn't correct.
Spoiler!
I understand the thought process - some sort of binary search algorithm.
If you had 7 balls, then yes, your algorithm would be optimal.
However, what happens if you drop on floor 50 and it breaks? What do you do next? All you know is that it may not break somewhere between floor 1 and 49, and you only have one ball left.
Technically speaking you didn't prove that Mod9( 2^x) follows a pattern
I don't know the exact notation for Mod notation.
But I believe you.
Spoiler!
It follows since multiplication works across mods.
ie. if a1=b1 mod c, and a2=b2 mod c, then a1a2=b1b2 mod c
Since we are talking powers of 2, after the 6th term in the loop, which is 5 mod 9, the next term will be 5*2=1 mod 9 and the cycle repeats.
Quote:
Originally Posted by Bring_Back_Shantz
To the new one
Spoiler!
I can get it as low as 19
Drop on 10, 20, 30 etc till one breaks, then start at 11, 21, 31 ect and drop each floor till it breaks, highest would be 19 drops:
10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 91, 92, 93, 94, 95, 96, 97, 98, 99
Using just straight multiples you get a max number of drops of
Interval = x (ie, if you're going to drop every 3rd floor, the interval (x) = 3
Max Drops for an interval = 100/x (rounded to the nearest whole number) + x-1
so for X = 2
Max Drops = 100/2 + 1 = 51
For x = 10
Max drops = 100/10 + 9 = 19
You get the same number of drops for 11 or 12
X = 11 = 100/11 + 10 = 9+10=19
x = 12 = 100/12 + 11 = 8 + 11 = 19
I can't remember the notation for truncating/rounding
Anyway, it's a minimum at an interval of 10-12
That being said, there is maybe another way to do it, but that's my quick crack at it.
Location: In my office, at the Ministry of Awesome!
Exp:
Quote:
Originally Posted by psyang
Spoiler!
It follows since multiplication works across mods.
ie. if a1=b1 mod c, and a2=b2 mod c, then a1a2=b1b2 mod c
Since we are talking powers of 2, after the 6th term in the loop, which is 5 mod 9, the next term will be 5*2=1 mod 9 and the cycle repeats.
It's a great start, but it is not optimal.
WRT the first one: I know it's correct, you just didn't have it explicitly in your proof, and showing that part is true is required to showing the final result is true.
I was just being a pedant.
WRT the second, I figured it wasn't optimal, but a good first pass/starting point. I'll have to think a bit more.
__________________
THE SHANTZ WILL RISE AGAIN. <-----Check the Badge bitches. You want some Awesome, you come to me!
<-----Check the Badge bitches. You want some Awesome, you come to me!
