Problem 361

jovo_amf · Post by **jovo_amf** » Fri Dec 09, 2011 8:54 pm

I just don't understand the problem
Can someone explain to me why A(12) = 18?

thundre · Post by **thundre** » Fri Dec 09, 2011 9:21 pm

jovo_amf wrote:Can someone explain to me why A(12) = 18?

T = 01101001100101101001011001101001...

A(12)=18 because 14 through 17 never appear in T.

14: 1110
15: 1111
16: 10000
17: 10001

18: 10010 does appear, so that is the next A.

mantonetti · Post by **mantonetti** » Thu Jan 26, 2012 11:16 pm

Maybe my English is not enough to understand the terms of the problem, but I think there is an error: the number 4 (bin 100) appears in the sequence in places T₄-T₆, while the number 5 (bin 101) appears in places T₃-T₅ (so before number 4), and therefore to A₄ should correspond n = 5 and to A₅ should correspond n = 4.
Of course maybe that I didn't understand in which way n is associated with A_n; can someone clarify, please?

Marcus_Andrews · Post by **Marcus_Andrews** » Fri Jan 27, 2012 12:32 am

The question isn't asking about which binary expressions appear before/after other binary expressions. {An} is a sorted sequence of integers such that those integers have binary expressions somewhere in the Thue-Morse sequence {Tn}. 4 and 5's binary representations exist in {Tn}, so 4 and 5 are included in the sorted sequence {An}.

Example: Putting aside the 0-case, A(100) = 3251 means that the 100th element of {An} is 3251. Similarly, the 12th element is 18.

mantonetti · Post by **mantonetti** » Fri Jan 27, 2012 12:41 am

That's fine! Now I understood! (At least, I hope

)

Many thanks!

ffff0 · Post by **ffff0** » Tue Jul 17, 2012 4:58 am

Just wonder how many memory is required for this problem since A(10^18) has more than 2*10^9 binary digits and there are more than 3*10^9 numbers of such length?

TripleM · Post by **TripleM** » Tue Jul 17, 2012 5:00 am

But you only need the last 9 digits

You will never need an excessive amount of memory for a Project Euler problem.

ffff0 · Post by **ffff0** » Tue Jul 17, 2012 5:04 am

I know, but right now I need to store all tree to know which number is the right one.

Will keep thinking.

Marcus_Andrews · Post by **Marcus_Andrews** » Tue Jul 17, 2012 2:02 pm

The problem is able to be solved in under a second and with very little memory usage.

ffff0 · Post by **ffff0** » Tue Jul 17, 2012 2:45 pm

Looks like I'll learn this method from solution thread after brute-forsing right answer.

thundre · Post by **thundre** » Wed Jul 18, 2012 8:05 pm

ffff0 wrote:Looks like I'll learn this method from solution thread after brute-forsing right answer.

My best-so-far solution (which I wouldn't call brute-force) bogged after 10¹⁴.

It is quite an interesting sequence.

ffff0 · Post by **ffff0** » Thu Jul 19, 2012 3:22 am

Last steps of my method are brute-force. It takes 30 minutes and 2 GB of RAM to get an answer.

Project Euler Forum

Problem 361

Problem 361

Re: Problem 361

Re: Problem 361

Re: Problem 361

Re: Problem 361

Re: Problem 361

Re: Problem 361

Re: Problem 361

Re: Problem 361

Re: Problem 361

Re: Problem 361

Re: Problem 361