Page 1 of 1
Problem 699
Posted: Mon Jan 27, 2020 1:24 pm
by pjt33
There's an error in the problem statement. It currently says
the denominator is a power of 3 i.e. $b=3^k, k>0$.
It should say
the denominator is a power of 3 other than 1, i.e. $b=3^k, k>0$.
(The other possible correction, $>$ to $\ge$, doesn't match up with the test cases).
Problem 699, error in provided example?
Posted: Sun Feb 02, 2020 7:47 pm
by sOvr9000
It is possible that I'm wrong, but I think there's an error in an example given in Problem 699. The example in question is T(100)=270.
The sigma function example is good, and a naive implementation of summing the factors of a positive integer will show that σ(10)=1+2+5+10=18.
The naive implementation to which I am referring is one where the square root (if it is an integer) of n is added twice. This incorrect implementation allows T(100)=270, but correcting the function to only count the square root once (if the square root is an integer) makes T(100)=258.
I specifically tested my factorization of 100, and when I was getting T(100)=270, I was counting the factor 10 twice. When I changed sigma to only count the square root once for general n, I got T(100)=258.
Am I just missing an important detail, or is my assumption correct that the square root should only be counted once?
EDIT: I also tested T(106). I got 26089275 instead of 26089287 using what I think is the correct sigma function, based on the definition given in the problem.
Re: Problem 699, error in provided example?
Posted: Sun Feb 02, 2020 8:36 pm
by hk
No, the given example is correct.
The triffle numbers not exceeding 100 are:
Code: Select all
n sigma sigma(n)/n
3 4 4/3
9 13 13/9
12 28 7/3
27 40 40/27
54 120 20/9
81 121 121/81
84 224 8/3
The answer for 10^6 is also correct.
There must be another error in your program.
(it is correct that the divisor 10 of 100 should only be added once.)