Project Euler Forum

Hi,
Can someone please post the sum from n = 1 to 50 of f(n)/n? I'm eight off the correct value for n = 1 to 100
Thanks!

I get 7517.

Ah excellent, thanks - I see where I went wrong now!
Damn you euler - you had to include f(9999) in the brief! I'm going to have to rethink the way I'm doing it now.

Damn you euler - you had to include f(9999) in the brief!

I agree with you it would be so much easier without it, btw is it possible to find f(9999) with an "ameliorated" brute force, or that's totally impossible (and I should find a clever solution ) ?

Answering your question would violate forum rules in my opinion.

http://projecteuler.net/index.php?secti ... ems&id=303
i solved the problem, but i wondered if anyone has a proof that every number has a 'nice' multiple... couldn't find one myself
thanks

From Problem 129 (View Problem):

Given that n is a positive integer and GCD(n, 10) = 1, it can be shown that there always exists a value, k, for which R(k) is divisible by n

where R(k) is the kth repunit, i.e. the number consisting of k ones.
As rathmann pointed out in the 303 forum, this shows it can be done with just ones (and possibly trailing zeroes to deal with the any factors 2 and 5) so you don't even need any twos.

Here's a quick proof:
Given any n coprime to 3.
Consider the sequence 10⁰ mod n, 10¹ mod n, 10² mod n, ...
There are no more than n different values these can have, so there must be repetitions.
So 10^a = 10^b mod n, for some a>b.
Therefore
10^a - 10^b is divisible by n
Since we chose n to be coprime to 3:
(10^a - 10^b)/9 is divisible by n
1111...11110000...0000 is divisible by n, where there are a-b ones and b zeroes.

To deal with factors of 3, you can use the fact that if a repunit R(k) is divisible by n, then R(3k) is divisible by 3n. This is because tripling the length of a repunit R(k) is the same as multiplying by 10^2k+10^k+1, which is a multiple of 3.

thank you

Regarding the numbers consisting only of nines, e.g. 9, 99, ... then
f(n) follows an interesting pattern ...
I don't know if it is provable...

Hello,

Can someone please post the sum from n = 1 to 1000 of f(n)/n? I have the right answer for n=100 but for n=10000 it doesn't seem I get the correct answer but I'm almost sure my method is correct.
Or maybe someone would be kind enough to allow me to send him my result for n=9990 and n =9999 and tell me if it's correct or not ?

Thanks,

Joël

The problem was what I thought, wrong values for n = 999 and n=9999 (not the smallest possible)

sinac wrote:Can someone please post the sum from n = 1 to 1000 of f(n)/n?

Can someone post the answer or PM it me please ?

Lotes wrote:

sinac wrote:Can someone please post the sum from n = 1 to 1000 of f(n)/n?

Can someone post the answer or PM it me please ?

I take it that you are joking.
However, there are idiots galore that would take this seriously.
So please refrain from this kind of joking.

mh however, you can delete the last 3 postings (including this one). i ve found my mistake. Problem solved

for 1 to 50 I get 7550...I dont see the mistake, anyone?

[(1, 2), (2, 10), (3, 12), (4, 12), (5, 10), (6, 12), (7, 21), (8, 112), (9, 12222), (10, 20), (11, 22), (12, 120), (13, 221), (14, 112), (15, 120), (16, 112), (17, 102), (18, 12222), (19, 1102), (20, 100), (21, 210), (22, 110), (23, 1012), (24, 120), (25, 100), (26, 1222), (27, 21222), (28, 112), (29, 1102), (30, 120), (31, 2201), (32, 1120), (33, 1122), (34, 102), (35, 210), (36, 22212), (37, 111), (38, 1102), (39, 10101), (40, 120), (41, 11111), (42, 210), (43, 2021), (44, 220), (45, 122220), (46, 1012), (47, 1222), (48, 1200), (49, 11221), (50, 100)]

xe3tec wrote:for 1 to 50 I get 7550...I dont see the mistake, anyone?

n itself is also a multiple of n (namely one times n).

edit: got it

jasa wrote:Regarding the numbers consisting only of nines, e.g. 9, 99, ... then
f(n) follows an interesting pattern ...
I don't know if it is provable...

f(n)/n also follows a predictable pattern for the 9's, there might be a function that gives f(n)/n for these numbers?