Problem 303

[Smaug]

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!

[LarryBlake]

I get 7517.

[Smaug]

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.

[Cerium]

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 ) ?

[hk]

Answering your question would violate forum rules in my opinion.

[poochon]

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

[jaap]

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.

[poochon]

thank you

[jasa]

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...

[sinac]

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

[sinac]

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

[Lotes]

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 ?

[hk]

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.

[Lotes]

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

[xe3tec]

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)]

[jaap]

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).

[xe3tec]

edit: got it

[whakamaru]

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?