Shlomi Fish avatar Shlomi Fish committed b287af6

Add the notes for euler_188.

Comments (0)

Files changed (1)

project-euler/188/euler-188-notes.txt

+Description:
+
+<QUOTE>
+
+The hyperexponentiation or tetration of a number a by a positive integer b, denoted by a↑↑b or ba, is recursively defined by:
+
+a↑↑1 = a,
+a↑↑(k+1) = a**(a↑↑k).
+
+Thus we have e.g. 3↑↑2 = 33 = 27, hence 3↑↑3 = 327 = 7625597484987 and 3↑↑4 is roughly 103.6383346400240996*10^12.
+
+Find the last 8 digits of 1777↑↑1855.
+
+</QUOTE>
+
+We are interested in 1777 ** (1777 ↑↑ 1854) % 1e8 . Now, (1777 ** n % 1e8)
+has a cycle, because for some n, ( (1777 ** n) % 1e8 ) == 1. Let's call this
+cycle $m.
+
+Now we are interested in (1777 ↑↑ 1854) % $m. This is
+1777 ** (1777 ↑↑ 1853) % $m . This too has a cycle which we'll call $t ,
+so we check 1777 ** (1777 ↑↑ 1852) % $t, and so on.
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.