Puzzle:

Given a function 'solve()' that accepts a single integer parameter, and returns an integer, write a program that determines if this function is an additive function [ solve($x+y$) = solve($x$) + solve($y$) ] for prime numbers below $100$.

In this case, $f(x+y)=f(x)+f(y)$ refers to an additive function, and the prime numbers below $100$ are $2, 3,5,7,11,13,17,19,23,29,31,37,41,43,47, \cdots,97$, so does that mean if $x=2$ and $y=5$ then $f(x+y)=f(x)+f(y$) holds true, and does it remains same for all pairs of prime numbers?

Please let me know if I am wrong.

• you seem to be right Jul 19, 2012 at 8:34
• btw the key optimization that you can make would be to keep a hash map x -> f(x) so that you don't recompute solve() for an argument more than once. eg. f(22) will come up as both f(11) + f(11) and also as f(3) + f(19). Although you need to compute these values like f(3) separately, you should have to compute f(22) only once. Jul 19, 2012 at 8:44
• The claim is ambiguously stated, but your interpretation looks likely. One alternative interpretation would only look at primes $x$ and $y$ for which $x+y$ is also prime, but that would be ridiculously restricted. Jul 19, 2012 at 8:46
• has anyone answer this question?
– user48728
Nov 9, 2012 at 0:14
• @Yoo No one asked a question. OP asked whether she was wrong, and was told she wasn't. If you have a question to ask, you've not gone about it very well. Nov 9, 2012 at 0:20