111..

1 = 1 x 1
111 = 3 x 37
111, 111, 111 = 9 x 12,345,679
111.....1 (27 1's) = 27 x 4,115,226,337,448,559,670,781,893

So it seems that it you have n 1's in a row, the number is a multiple of n.. if.. and only if?.. n is 3^0, 3^1, 3^2, 3^3 etc. It holds true for n = 3^4 = 81 too. And there are no small values of n that would not be powers of 3 for which 111...1, n 1's, would be a multiple of n.

How about big values of n?

Originally posted by talzamir
1 = 1 x 1
111 = 3 x 37
111, 111, 111 = 9 x 12,345,679
111.....1 (27 1's) = 27 x 4,115,226,337,448,559,670,781,893

So it seems that it you have n 1's in a row, the number is a multiple of n.. if.. and only if?.. n is 3^0, 3^1, 3^2, 3^3 etc. It holds true for n = 3^4 = 81 too. And there are no small values of n that would not be powers of 3 for which 111...1, n 1's, would be a multiple of n.

How about big values of n?

Well known for 3 and 9, yes. But also for 27, 81, 243 etc?

And showing that a number that looks like a string of n ones is NOT divisible is n is not a power of 3.. is also a bit less well known.

Anyhow.. 7....7 = 7 x (10^81-1) / 9.. yup, divisible by 81x7 = 567.

There may be something in the following, not sure....

111...111 (with n ones) = 10^0 + 10^1 + 10^2 + ... + 10^(n-1)

if divisible by n then
10^0 + 10^1 + 10^2 + ... + 10^(n-1) = n * m

taking both sides mod 3, and remembering 3 goes into 9 and 99 and 999 etc so each term on the left is 1 mod 3

n mod 3 = (n * m) mod 3

this means that the difference betwen n and m*n must be divisible by 3

(n*m - n) = 3k

n(m-1) = 3k

bit stuck there, still thinking

As for showing it does work for n = 3^0, 3^1 ..

obviously it works for n = 3^0 = 1. 1/1 = 1, no fractions.

so it works for n = 3^k at least up to some value of k. Going from k to k+1..

1...1 = 3^k * some integer x
111...111 is a sequence three times as long, consisting of 3^(k+1) = 3^k times 3 1's. But it can be divided by 1...1, and yields 10...010...01.

e.g. 111,111,111 = 111 x 1,001,001

and because 1,001,001 is a multiple of 3, say, it's 3 times some integer y,

111...111 = 1...1 x 100...00100...001 = 3^k * x * 3 * y = 3^(k+1) xy.

so it is divisible by 3^(k+1).

That, with some polishing, proves it for 1, 3, 9, 27, 81 etc.

11 is not divisible by 2, not 1111 by 4, nor 11111 by 5.. but is that just chance? Can't (10^n -1) / 9 be divisible by n ever if n isn't a power of 3..?

All numbers that aren't powers of 3 are either non-3 primes or compound numbers that include a non-3 prime as factor. If that prime is a factor then

(10^n -1) / 9 = zero mod n
10^n - 1 = zero mod n
10^n = 1 mod n

..and that's how far I've gotten so far.

Aha! This was so difficult to prove true that I thought I would write a little search program to attempt to disprove it. It found that are some numbers (e.g. 111 ones) that are divisible by n but are not powers of 3, this is because 111 goes into any number which is a multiple of 3 ones, and 111 ones is 3*37 ones.

My perl script found:
1 ones (1) gives a number divisible by 1, which is 3^0
3 ones (111) gives a number divisible by 3, which is 3^1
9 ones gives a number divisible by 9, which is 3^2
27 ones gives a number divisible by 27, which is 3^3
81 ones gives a number divisible by 81, which is 3^4
111 ones gives a number divisible by 111, which is not 3^5 !!
243 ones gives a number divisible by 243, which is 3^5
333 ones gives a number divisible by 333, which is not 3^6 !!
729 ones gives a number divisible by 729, which is 3^6
999 ones gives a number divisible by 999, which is not 3^7 !!
2187 ones gives a number divisible by 2187, which is 3^7
2997 ones gives a number divisible by 2997, which is not 3^8 !!
4107 ones gives a number divisible by 4107, which is not 3^8 !!
6561 ones gives a number divisible by 6561, which is 3^8
8991 ones gives a number divisible by 8991, which is not 3^9 !!
12321 ones gives a number divisible by 12321, which is not 3^9 !!
13203 ones gives a number divisible by 13203, which is not 3^9 !!

4107 looks weird, it is 37*111 or 3*37^2, (111 is 3 * 37)

No wonder it was so hard to prove it applies only to 3^k =)

According to oeis.org, 1, 3, 9, 27, 81, 111, 243, 333, 729, 999, 2187, 2997, 4107, 6561, 8991, 12321, 13203, 19683, 20439, 26973, 36963, 39609, 59049, 61317, 80919, 110889, 118827, 151959, 177147, 183951, 242757, 332667, 356481, 455877, 488511, 531441, 551853, 728271

are the first solutions n for 10^n - 1 being a multiple of n.. not exactly the same problem, but very close.

Factorised they are:
1 = 3^0
3 = 3^1
9 = 3^2
27 = 3^3
81 = 3^4
111 = 3.37
243 = 3^5
333 = 3^2.37
729 = 3^6
999 = 3^3.37
2187 = 3^7
2997 = 3^4.37
4107 = 3.37^2
6561 = 3^8
8991 = 3^5.37
12321 = 3^2.37^2
13203 = 3^4.163

So although the chains of 1's that are the length of a power of 3 are always prime, and when not an exact prime they seem to often have a length that is a power of 3 times a power of 37, it looks like as the chains get longer other prime powers are going to arise, starting with a powers of 3 times 163. Going from your list, the next odd one is 20439, which is 3^3.757

by the way, the perl search program that found the lines that broke the rule was:

use strict;
use warnings;

use bigint;

my $n = Math::BigInt->new(1);
my $power = 0;
my $power_of_3 = 1;
while () {
my $ones = $n;
$ones = (10**$ones -1)/9;
if ($ones % $n == 0) {
my $string = ($n < 6) ? "($ones) " : "";
if ($n == $power_of_3) {
print "$n ones ".$string."gives a number divisible by $n, which is 3^$power\n";
$power++;
$power_of_3 *= 3;
}else {
print "$n ones ".$string."gives a number divisible by $n, which is not 3^$power !!\n";
}
}
$n++;
}

Seems hard to make a complete list, or even a rule with which to generate a complete list. 3^n . 37^m covers quite a few cases. But then there's 13,203 which introduces a new prime to the mix. After that there are more primes that will eventually be required. According to oeis.org, which looks at the 999....9 sequence, the primes below one million that feature are 3, 37, 163, 757, 1999, 5477, 8803, 9397, 13627, 15649, 36187, 40879, 62597, 106277, 147853, 161839, 215893, 231643, 281683, 295759, 313471, 333667, 338293, 478243, 490573, 607837, 647357, and 743933.

Yeah, you are looking for the (probably infinite) set of primes that are factors of (10^n-1)/3 for some integer n.

If you could generate that list "quickly" you would have a way of generating an infinite list of primes, so I suspect it is not possibly to generate except by a brute force search.

I reckon so too. If there were some iterative method, this would be a way to get huge primes in a manner comparable with getting mersenne primes.. and it would be rather odd to find that the sequence is finite. So, unsatisfying as it is.. brute force is all we are left with for now.