Large

[cinelli]

Using no more than a non-programmable calculator, find the prime factors of the following 20-digit number:

12 318 876 808 768 112 319

Cinelli

[UncleEbenezer]

OK, the 3*3*3*3*11 fall out of the familiar base-10 patterns.

For the rest, is there some neat trick beyond exhaustive search up to finding 271, whereupon we're past the square root of 9091? If not, I'll call the problem too tedious to do without programmatic aid.

(As a teenager I earned a few bob doing unskilled factory work. Part of that involved a counter that ticked up as I performed a repetitive task. As a distraction, I got quite adept at factoring numbers within a couple of seconds. But that wasn't a 20-digit counter).

[psychodom]

I agree with UncleEbenezer, unless I'm missing something fundamental, this is just brute-force tedium?

factors of 3,3,3,3,11 drop out by inspection/hand

we're then left with:
13,825,899,897,607,309
which, at 17 digits, is still too large for MS Calculator to handle

liberal hand-waving at the point finds us the next repeated factors of 41, 41 leaving:
8,224,806,601,789
which, at 13 digits, is large enough for MS Calculator to handle

Judicious use of the MR function and trial and erroring prime factors give us:
97,127,271,271,9091

I hope there's a more elegant solution!

-Dom

[UncleEbenezer]

is still too large for MS Calculator to handle
-Dom

But not for the commandline calculator bc, which dates from 1975. I guess MS has some catching up to do.

Nor for a regular 64-bit integer, making it programmatically trivial

[cinelli]

If not, I'll call the problem too tedious to do without programmatic aid.

No, this is not a brute force problem. When you have the solution I hope you will agree it's very elegant.

Cinelli

[psychodom]

Thanks Cinelli for clarifying that it's not a brute force problem.

All those repeated factors gave me a clue.
Observe that 3 x 3 x 41 x 271 = 99999
that's surely not a coincidence....

If we put some commas in an unorthodox fashion, as follows:
12318,87680,87681,12319

there's definitely a pattern going on here,
and observe that if we let
n = 12319
then
10^5 - n = 87681

ok, this looks promising

we can reformulate
N = 12318,87680,87681,12319
N = 10^15(n-1) + 10^10(10^5 - n -1) + 10^5(10^5 - n) + n
N = (10^15 - 10^10 - 10^5 +1)n
N = (10^10 - 1)(10^5 - 1)n
N = (10^5 + 1)(10^5 - 1)(10^5 - 1)n
N = 100001 x 99999^2 x 12319

now time for the calculator!

N = (11 x 9091) x (3 x 3 x 41 x 271)^2 x (97 x 127)

as required.

-Dom

[cinelli]

Brilliant, Dom. I was ready to give a hint - "let n = 12319" - but it wasn't needed.

Cinelli

[Gengulphus]

Using no more than a non-programmable calculator, find the prime factors of the following 20-digit number:

12 318 876 808 768 112 319

I've come to this thread way too late, but to give the most elegant way of expressing the solution I know: the well-known "a number is divisible by 9 if the sum of its digits is divisible by 9" test generalises to any base as "in base B, a number is divisible by B-1 if the sum of its digits in divisible by B-1".

Apply that in base 10,000,000,000, in which the number concerned has two 'digits', namely 1,231,887,680 and 8,768,112,319. They add to 9,999,999,999, so it is divisible by 9,999,999,999 - specifically, it is 9,999,999,999 * 1,231,887,681. Then apply it in base 100,000 to each of those factors and you find they're both divisible by 99,999, leading to the factorisation 100,001 * 99,999 * 12,319 * 99,999.

Taking out the obvious factors of 3*3 from each occurrence of 99,999, and the easy factor of 11 from 100,001 (using the fairly well-known test that a number is divisible by 11 if the sum of its even digits differs from the sum of its odd digits by a multiple of 11) gets us to 3 * 3 * 3 * 3 * 11 * 9,091 * 11,111 * 11,111 * 12,319. It's then a matter of brute force trial division with the calculator as far as I am aware, as psychodom indicates, but with the biggest of those factors being less than 111^2 = 12,321, not all that much force is required - it's a bit tedious, but with there only being 29 prime numbers under 111, nothing worse than that.

Gengulphus