Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member talzamir
    Art, not a Toil
    02 Sep '13 07:46
    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?
  2. Standard member DeepThought
    Losing the Thread
    02 Sep '13 10:28
    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?
    Yes, this is the old trick for summing the digits to test divisibility by 3.

    What is more:

    777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777, 777 is divisible by 567.
  3. Standard member talzamir
    Art, not a Toil
    02 Sep '13 13:26
    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.
  4. 08 Sep '13 17:56 / 1 edit
    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
  5. Standard member talzamir
    Art, not a Toil
    11 Sep '13 22:07
    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.
  6. 13 Sep '13 20:01 / 1 edit
    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)
  7. Standard member talzamir
    Art, not a Toil
    13 Sep '13 20:54
    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.
  8. 14 Sep '13 10:43 / 1 edit
    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
  9. 14 Sep '13 14:37
    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++;
    }
  10. Standard member talzamir
    Art, not a Toil
    14 Sep '13 14:45 / 1 edit
    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.
  11. 14 Sep '13 15:59
    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.
  12. Standard member talzamir
    Art, not a Toil
    15 Sep '13 15:24
    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.