Euler's totient function (n) is defined as the number of positive integers not exceeding n that are relatively prime to n, where 1 is counted as being relatively prime to all numbers. So, for example, (20) = 8 because the eight integers 1, 3, 7, 9, 11, 13, 17, and 19 are relatively prime to 20.

Euler's totient valence function v(n) is defined as the number of positive integers k such that (k) = n. For instance, v(8) = 5 because only the five integers k = 15, 16, 20, 24, and 30 are such that (k) = 8. The table below shows values of v(n) for n 16. (For n not in the table, v(n) = 0.)

n | v(n) | k such that (k) = n |
---|---|---|

1 | 2 | 1, 2 |

2 | 3 | 3, 4, 6 |

4 | 4 | 5, 8, 10, 12 |

6 | 4 | 7, 9, 14, 18 |

8 | 5 | 15, 16, 20, 24, 30 |

10 | 2 | 11, 22 |

12 | 6 | 13, 21, 26, 28, 36, 42 |

16 | 6 | 17, 32, 34, 40, 48, 60 |

Evaluate v(2^{1000}).

A solution will be posted as soon as possible.

Source: Original