[Community Puzzle] The G Note - Puzzle discussion

Puzzles
#1

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @pepper,validated by @kitarotao,@SlowSnakPierre and @SkyWhait.
If you have any issues, feel free to ping them.

#2

Hello there,

Maybe it’s because I haven’t solved it yet (I just have a trivial solution that works only for low numbers for now), but I don’t see how it’s related to the Note G?

If it’s not a spoil of the solution, would someone care to explain how it is?
Thanks

#3

Hi @Senua :slight_smile: Note G is a computer algorithm written by Ada Lovelace that was designed to calculate Bernoulli numbers using the hypothetical analytical engine. And it is related in some way with a task. However research is the most important part of this puzzle in my view, so try figure it out :wink:
Here you can find details: Wikipedia Note G

Although my solution passed all the tests, I feel it’s not the right one - it’s more of a hack. I’m waiting for someone to share the correct solution. So far, no one has posted it yet. :frowning:

#4

Hello @Senua ,

I have solved this puzzle, and Note G did not help me at all.

Looking back at my code, it actually computes some values that are mentioned in the note, but only relies on:

  • recursion (as mentioned in the tags)
  • big integers (64-bits integers are not big enough for my approach)
  • three well-known formulas/algorithms on integers (things I have already used several times on CodinGame).

And I also use a hack at the end of my code. If the modulus were a prime number (as it usually is in this kind of puzzle), this hack would not be needed and the statement would be less misleading (I can’t help thinking about using double-precision floating-point numbers when I see 2^53).

#5

I still timeout in the last IDE test in PHP, despite I don’t calculate n^n^n, but use a formula with just n iterations, and in total I use O(n^2) arithmethic operations. But these arithmethic operations are slow because I had to use the quite slow bcmath library for arbitrary precision and a custom arbitrary precision BCFraction class implementation (as php has no built-in support for fractions, nor arbitrary precision fractions). I also use memoization, not repeating calculations for some required partial results.
I am not sure what additional math idea I miss here. I checked the wikipedia page of Note G, which directed me to the wiki page of B… number, which directed me to F… formula and of course there is the algorithm to calculate the B… coefficients.

EDIT: after replacing an accidental bcpow() call with bcpowmod() and some further optimisations my code runs faster, but I still need 29 sec locally for n=513, so only a code with hardcoded lookup values passes everything online…
EDIT2: After solving this with the above caveat, I checked the example solution on contribution and it is very underwhelming. Only works because of built-in fast arbitrary precision fraction library… Does not even apply modulo on partial results, only on the huge end result…

1 Like