Algorithm for Consecutive Composite Numbers
Carl G.
task: Write down as many positive consecutive integers as you can in 10
minutes, where every number in the list is composite (non-prime). You only
have a pencil and a pad of paper, and haven't been told the task beforehand
(otherwise you would have just memorized the starting and ending numbers of
a very large list). The list must include every consecutive integer
(stepping by one), from the smallest number on your list to the greatest,
and none of the integers may be prime. Calculations may be performed on
separate sheets of paper. You may work in any base(s) you choose (e.g.,
base ten or base two), but every digit of every number must be written out
separately (e.g., you can't just give the first and last number of the range
of consecutive numbers).
What strategy and procedure would you follow to generate your list?
How many consecutive composite numbers _can_ you list in under 10 minutes
using only pencil and paper as tools? Start as quickly as possible, as if
you just heard the task. If you post your result, it is only necessary to
give the numbers on each end of the range, I'll trust that you actually
wrote all of your numbers down.
How would you change your strategy if both you and your opponent were
allowed to use a 10-digit calculator that supported only addition,
subtraction, multiplication, division, and the square root?
How many consecutive composite numbers _can_ you produce in under 10 minutes
if you were also allowed to use a calculator to perform the functions stated
above?
I'm interested in both strategies and in actual results. If you don't wish
to actually spend 10 minutes trying to generate and list the numbers, just
give the strategy you would use if you ever were in such a competition.
Carl G.
Rory Molinari
Carl> During a competition, you and your opponent are both given the
Carl> following task: Write down as many positive consecutive integers
Carl> as you can in 10 minutes, where every number in the list is
Do I have to write down each integer in its full decimal expansion, or
can I write down things like "2^3 + 5" or "123*17"?
Rory
Virgil
<cgi...@microprizes.com> wrote:
It is possible to create an arbitrarily long list of composites if you
have sufficient time and calculating ability.
Let n! = n "factorial" = the product of the positive whole numbers from
1 up through n.
Then the numbers from (n! + 2) up through (n! + n) are all composites,
being divisible by 2 through n, respectively.
So if you want m consecutive composites, start with ((m+1)! + 2).
Martin Julian DeMello
> It is possible to create an arbitrarily long list of composites if you
> have sufficient time and calculating ability.
> Let n! = n "factorial" = the product of the positive whole numbers from
> 1 up through n.
> Then the numbers from (n! + 2) up through (n! + n) are all composites,
> being divisible by 2 through n, respectively.
> So if you want m consecutive composites, start with ((m+1)! + 2).
That was my immediate idea (based, of course, on Euclid's prime number
proof), but it'd be startlingly inefficient in practice, since you'd
actually have to write the numbers out digit by digit. Not to mention
calculating the factorial in the first place.
Of course (sillyish spoiler)
No one said you had to work in base 10
Therefore I'll work in base m! and my numbers are
12, 13, 14, 15, 16 and so on until I run out of time. I certainly won't
overflow the 1s place :)
--
Martin DeMello
Geoff Bailey
In article <90ha95$6g3$1...@slb3.atl.mindspring.net>,
Carl G. <cgi...@microprizes.com> wrote:
> During a competition, you and your opponent are both given the following
> task: Write down as many positive consecutive integers as you can in 10
> minutes, where every number in the list is composite (non-prime).
[ ... ]
> You may work in any base(s) you choose (e.g., base ten or base two),
> but every digit of every number must be written out separately
Heh. I wanted to use a huge base but then I couldn't work out what
symbols to use for the 'digits'. :) I don't think it is worth the
effort to change bases, as it would cause me to have to think more
about the numbers as I wrote them down. However, if I am allowed to
write 'digits' like (13), I would definitely do so, since there is no
real base changing going on.
> What strategy and procedure would you follow to generate your list?
I got 55 numbers, from 7420738134796 to 7420738134850. I was midway
through prepending 7420738134795 when I ran out of time. My procedure
was simple: calculate the product, T, of small primes (in this case,
up to 37) and then write down T + 2, ..., T + 40. If time permits, I
was going to prepend down to T-40. Note that T + 1 and T - 1 were not
proved composite, but were so likely to be so that it is a risk I was
willing to take. (And, in fact, these are composite.)
> How would you change your strategy if both you and your opponent were
> allowed to use a 10-digit calculator that supported only addition,
> subtraction, multiplication, division, and the square root?
I would probably have used the primes up to 47 instead, giving a value
of T = 614889782588491410, and a spread of 105 composites (starting at
T + 2 .. T + 52, then working down from T + 1 to T - 52). Again, these
are all composite. At this point the time to write down the numbers is
going to vastly dominate, so finding larger numbers is not worth the
effort. However, it appears I would have been better off using the
smaller set and writing more of it out, as I would only have got about
70 of them done in the remaining time.
_If_ I am allowed to specify that I am writing my numbers in base
(T - 52), then I could get them all done quite easily, as (1)(54),
(1)(55), etc. In that case I would probably have taken the extra effort
to choose a T such that T +- 1 are composite. Working mod 53 and 59 I
can find a suitable multiplier (in this case, 850) to ensure the desired
condition, yielding T = 522656315200217698500.
I would then state that I was working in base (T - 52), and write down
the 105 numbers (1)(0), ..., (1)(105).
Cheers,
Geoff.
-----------------------------------------------------------------------------
Geoff Bailey (Fred the Wonder Worm) | Programmer by trade --
ft...@cs.usyd.edu.au | Gameplayer by vocation.
-----------------------------------------------------------------------------
Carl G.
Virgil wrote in message ...
>In article <90ha95$6g3$1...@slb3.atl.mindspring.net>, "Carl G."
><cgi...@microprizes.com> wrote:
>
>> During a competition, you and your opponent are both given the following
>> task: Write down as many positive consecutive integers as you can in 10
>> only
>> have a pencil and a pad of paper, and haven't been told the task
>> beforehand
>> (otherwise you would have just memorized the starting and ending numbers
>> of
>> a very large list). The list must include every consecutive integer
>> (stepping by one), from the smallest number on your list to the greatest,
>> and none of the integers may be prime. Calculations may be performed on
>> base ten or base two), but every digit of every number must be written
>> out
>> range
>> of consecutive numbers).
>>
>>
>> using only pencil and paper as tools? Start as quickly as possible, as
>> if
>> you just heard the task. If you post your result, it is only necessary
>> to
>> give the numbers on each end of the range, I'll trust that you actually
>> wrote all of your numbers down.
>>
>> allowed to use a 10-digit calculator that supported only addition,
>> subtraction, multiplication, division, and the square root?
>>
>> minutes
>> if you were also allowed to use a calculator to perform the functions
>> stated
>> above?
>>
>> I'm interested in both strategies and in actual results. If you don't
>> wish
>> to actually spend 10 minutes trying to generate and list the numbers,
>> just
>> give the strategy you would use if you ever were in such a competition.
>>
>> Carl G.
>>
>
>have sufficient time and calculating ability.
>
>Let n! = n "factorial" = the product of the positive whole numbers from
>1 up through n.
>
>Then the numbers from (n! + 2) up through (n! + n) are all composites,
>being divisible by 2 through n, respectively.
>
>So if you want m consecutive composites, start with ((m+1)! + 2).
This may give a large range, but it not be a very good strategy for the
contest. For example, there is at least one range of 5 digit numbers that
contains 70 composite numbers (can you find it without using a computer?).
The whole range could be written using 350 characters (in base 10). All 70
of these numbers could probably be written down within the 600 seconds
(assuming you could find the starting and ending numbers quickly enough).
((70+1)!+2) has over 100 digits. You may only be able to write ten of the
numbers (>1000 digits) in the allowed time. Also, calculating 71 factorial
may take a good portion of your time (unless you have it memorized).
Carl G.
Kevin N. Stone
55 seems a little small, surely starting at 1 you stand a better chance?
Kev
jamj...@my-deja.com
> No one said you had to work in base 10
>
> Therefore I'll work in base m! and my numbers are
>
> 12, 13, 14, 15, 16 and so on until I run out of time. I certainly
won't
> overflow the 1s place :)
>
> --
> Martin DeMello
>
Actually, the problem stated that you could choose your base. Provided
you do not have to choose your base beforehand, this would be a great
strategy. When you have only a couple seconds left, you quickly write
down your base, which is (the last one's digit) factorial. If you run
out of distinct characters, you just bust in with the subscript. What a
great solution!
Sent via Deja.com http://www.deja.com/
Before you buy.
Geoff Bailey
In article <nBbX5.5628$Eb5.25989@news2-hme0>,
Kevin N. Stone <brainb...@ic24.net> wrote:
> 55 seems a little small, surely starting at 1 you stand a better chance?
No, the problem asked us to write down consecutive composite numbers.
(i.e., x, x+1, x+2, ...). There are too many small prime numbers for
using a random short number to be viable.
As an aside, there is a good range of 123 usable numbers from 10^16 - 62
to 10^16 + 60, whose form should make them easy to remember if anyone
needs to do this in practice. Of course, it would be very easy to
accidentally drop a 0 if not allowed to change the base.
Courtenay Footman
>
>In article <nBbX5.5628$Eb5.25989@news2-hme0>,
>Kevin N. Stone <brainb...@ic24.net> wrote:
>> 55 seems a little small, surely starting at 1 you stand a better chance?
>
>No, the problem asked us to write down consecutive composite numbers.
>(i.e., x, x+1, x+2, ...). There are too many small prime numbers for
>using a random short number to be viable.
>
>As an aside, there is a good range of 123 usable numbers from 10^16 - 62
>to 10^16 + 60, whose form should make them easy to remember if anyone
>needs to do this in practice. Of course, it would be very easy to
>accidentally drop a 0 if not allowed to change the base.
>
not clear from the description exactly what form the numbers have to
written in; just that they have to be written out in full. My strategy
would be to write down
1111!
1111!
1111!
etc. down the length of the page, go back to the top, write + signs after
each 1111! (1, not 0, because I can write 1's faster), and then start
counting from 2 on up. When I hit the bottom of a column, repeat.
I do not want to actually do this without a substantial cash incentive,
because my hand would be aching by the time I finished, but I submit
that this is a valid method to solving the problem given.
--
Courtenay Footman I have again gotten back on the net, and
c...@lightlink.com again I will never get anything done.
(All mail from non-valid addresses is automatically deleted by my system.)
Geoff Bailey
In article <slrn92uca...@adore.lightlink.com>,
Courtenay Footman <c...@adore.lightlink.com> wrote:
> In ten minutes, I would hope to get far more than 123 numbers. It is
> not clear from the description exactly what form the numbers have to
> written in; just that they have to be written out in full. My strategy
> would be to write down
>
> 1111!
> 1111!
> 1111!
>
> etc. down the length of the page, go back to the top, write + signs after
> each 1111! (1, not 0, because I can write 1's faster), and then start
> counting from 2 on up. When I hit the bottom of a column, repeat.
The original post said:
You may work in any base(s) you choose (e.g., base ten or base two),
but every digit of every number must be written out separately [...]
I took this to mean that no formulas or shorthands are allowed. That
is, you may not write 1111!, you must write down all the digits of this
number instead. Now, the line about working in whichever base you please
would imply that you could say you were working in base 1111!, but then I
claim that you would still have to write the base out in full once.
[ Carl? Care to state your intentions on this? ]
> I do not want to actually do this without a substantial cash incentive,
> because my hand would be aching by the time I finished, but I submit
> that this is a valid method to solving the problem given.
My hand was sore, but I got over it. :)