Back

Graham's Number

Worth 6 point(s) - Runtime Limit: 1 seconds

Introduction

Graham’s number is the largest number ever used in a mathematical proof (as of 1980). This number is astronomically huge, much bigger than googol (10100), googolplex (101010 ), and even googolgoogolplex. Graham’s number is so big, that a base 10 digit representation with each digit occupying a Planck volume would not fit inside the observable universe. To represent Graham’s number, Knuth’s arrow notation must be used. Much like how multiplication is repeated addition and exponentiation is repeated multiplication, tetration is repeated exponentiation, pentation is repeated tetration, and so on. Knuth’s up-arrow notation is commonly used to represent higher order operations. In this notation, a ↑ b represents exponentiation, a ↑↑ b represents tetration, a ↑↑↑ b represents pentation, and so on. Soon, the amount of arrows will be too much to write, cueing a shorthand notation: a ↑n b where n is the number of arrows in the longhand equivalent. For example, a ↑4 b = a ↑↑↑↑ b.
To define Graham’s number, we can use the following recursive function:

g(n) = 3 ↑g(n-1) 3
g(1) = 3 ↑↑↑↑ 3
g(64) = Graham’s number

To evaluate g(1), know that 3 ↑n 3 = 3 ↑n-1 (3 ↑n-1 3). So 3 ↑ 3 = 27 and 3 ↑↑ 3 = 327 ≈ 7.62 trillion. 3 ↑↑↑ 3 can be represented by 3 to the power of itself 7.62 trillion times. 3 ↑↑↑↑ 3, or g(1), can be represented by 3 tetrated by itself 3 ↑↑↑ 3 times. The number of arrows in g(n) is g(n-1), so this sequence explodes very quickly. Graham’s number is g(64). Write a program that determines if certain integers are factors of Graham’s number.

Input:
The first integer D indicates the number of test cases. The next line contains D integers which should be checked.

Output:
Print “Graham's Number is divisible by: ” followed by the divisors of Graham’s number found in the input in ascending order with no duplicates and a space between numbers.

Sample Input

6
2 6 3 4 3 5

Sample Output

Graham's Number is divisible by: 3