wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Notepad calculator
        
(Message started by: Mike_V on Oct 5th, 2003, 1:22pm)
Title: Notepad calculator
Post by Mike_V on Oct 5th, 2003, 1:22pm
This is a sorta weird one I guess.

So you're working on your friend's computer, and he's really anal about keeping it "clean" and thus the only program he has on it is notepad. (Essentially, any basic text editor will do.) But your class is in 2 minutes and you need to find out whether or not the following number is divisible by 3. Can you find out using only notepad and less than 2 minutes?

5234521253294075195782195895101563285726085765101563150832756081657150628756120835761780563856180563105862150823765082176582356128567180561281375821483242109835278658965487315671806578165872368751786645389063442143257109534985718945734587323767287984387473652718288375617515623875737150621587261587283715856432334567875433435563739829918773875761087510978737656764847863676721985656981569569569426756767176676161520987356215892839656891256893265982656195897265263547828523819846238159872365029856214987291562376519285328950710593275983427598710957912085791827529305701957190501010592357901050210502300253523211111112385923573298569382756982995782576747778382987561251123453589112345678901235929809530827591985893474589326298058917509175901578120935333

(Note: that weird space at the end is irrelevent, I did not mean it to be there.)
(Note 2: you don't have to figure out the method in 2 minutes, you just have to be able to complete the method in 2 minutes or so.)
Title: Re: Notepad colculator
Post by Sir Col on Oct 5th, 2003, 1:39pm
It's probably not the best method, but it might work in about 2 minutes...

::[hide]
Based on the property that a number is divisible by 3 iff the sum of its digits is divisble by 3, you could do the following:
(i) work through the list of digits and remove multiples of 3 (0, 3, 6, and 9).
(ii) replace the remaining digits with the remainder after division by 3; so 5[to]2, 7[to]1, and so on.

(iii) count the number of 1's (a) and the number of 2's (b).
(iv) if a+2b is divisible by 3, then the original number was.

OR

(iii) remove three 1's at a time, then remove three 2's at a time.
(iv) if the sum of the remaining digits is divisible by 3, then the original number was.
[/hide]::
Title: Re: Notepad colculator
Post by towr on Oct 5th, 2003, 2:02pm
yep, that's basicly the easiest way I think. [hide]Just removes any number divisable by three, every set of three equal numbers, every sequence of three following numbers, basicly any set of numbers that sum to a multiple of three and which is easy enough to see

note that using search can help a lot in speeding things up. something like replace even more (but that's not in notepad)[/hide]
Title: Re: Notepad calculator
Post by Icarus on Oct 5th, 2003, 2:11pm
Replace is in Notepad. It's ctrl-h. I have cause to use it on a fairly regular basis.

By the way, I tried this method. It took a lot longer than 2 minutes and I'm not too sure I didn't mess up in the middle anyway. (The result I got was that it [equiv] 2 mod 3.)
Title: Re: Notepad calculator
Post by Sir Col on Oct 5th, 2003, 2:31pm
What a super idea, Icarus!

It took me 58 seconds, and I did it in the following way:
(a) Replace ' ', with <empty>.
(b) Replace '0', '3', '6', and '9', with <empty>.
(c) Replace '4' and '7' with '1'.
(d) Replace '5' and '8' with '2'.
(e) Randomly replace '12', '21', '111', and '222' with <empty>.

I was left with nothing, so it appears that the number divides by 3. I then checked by writing a programme to add the digits and they add to 3588=3*1196.
Title: Re: Notepad calculator
Post by Icarus on Oct 5th, 2003, 2:38pm
The idea was Towr's, and you clearly were wiser than I in implementing it. I did the replacements a-d, but then I stopped and just started deleting 2's counting off three at a time. When I finished, I divided the 1s into equal lines, deleting sets of three lines together. This is why it took me so long. Your method of handling the 1s and 2s is so obvious now that I am chagrined not to have seen it. :-[
Title: Re: Notepad calculator
Post by Rezyk on Oct 5th, 2003, 3:59pm
I think it's better to use '11' instead of '2'.  Then for the last step all you need is '111' [to] ''.
Title: Re: Notepad calculator
Post by Mike_V on Oct 5th, 2003, 4:05pm

on 10/05/03 at 15:59:41, Rezyk wrote:
I think it's better to use '11' instead of '2'.  Then for the last step all you need is '111' [to] ''.


That's a great idea! One step back, then all the way forward.
Title: Re: Notepad calculator
Post by Sir Col on Oct 5th, 2003, 5:13pm

on 10/05/03 at 14:38:47, Icarus wrote:
The idea was Towr's

Oops, I didn't see his hidden part; sorry, towr.

What an inspired thought, Rezyk!

By the way, that was a super puzzle, Mike_V.
Title: Re: Notepad calculator
Post by Mike_V on Oct 5th, 2003, 6:14pm
Thanks, it was inspired while I was working on your expansion of T&B's n! problem. (Before I remembered the clue.)

And actually, thanks to Rezyk's idea, this method also is very viable for divisibilty by 9.
Title: Re: Notepad calculator
Post by towr on Oct 5th, 2003, 11:31pm

on 10/05/03 at 14:11:47, Icarus wrote:
Replace is in Notepad. It's ctrl-h. I have cause to use it on a fairly regular basis.
It's not in my notepad  :-/
Title: Re: Notepad calculator
Post by towr on Oct 5th, 2003, 11:34pm

on 10/05/03 at 15:59:41, Rezyk wrote:
I think it's better to use '11' instead of '2'.  Then for the last step all you need is '111' [to] ''.
If you just replace every number be 1's (so replace fi 5 by 5 1's), then you can check any divisability.
it's divisable by n if you're not left with anything after replacing all sequences of n 1's by nothing..
Title: Re: Notepad calculator
Post by Rezyk on Oct 6th, 2003, 12:25am

on 10/05/03 at 23:34:42, towr wrote:
If you just replace every number be 1's (so replace fi 5 by 5 1's), then you can check any divisability.
it's divisable by n if you're not left with anything after replacing all sequences of n 1's by nothing..


I think that only works for n [in] {1, 3, 9}.  Questions such as "Is 32 divisible by 2?" and "Is 33 divisible by 2?" would get answered incorrectly.
Title: Re: Notepad calculator
Post by towr on Oct 6th, 2003, 1:12am
hmm.. yes, you're right.. I didn't think straight for a moment.. (it happens.. (quite a lot))
Title: Re: Notepad calculator
Post by Sir Col on Oct 6th, 2003, 3:22am
I know that feeling all too well, towr. I must say that I read your original suggestion and was all ready to click 'Reply' to congratulate your insight, then Rezyk, in his/her 2nd post, makes another sharp observation.

By the way, welcome to the forum, Rezyk.
Title: Re: Notepad calculator
Post by Mike_V on Oct 6th, 2003, 4:21am
Haha, yep. I too jumped on that idea for a sec.

The question is then, is there a way to check for multiple divisibilities without actually dividing the number? ie can we use some version of this method to check for divisibility by 27? (Since 27 doesn't have the property that (the sum of the digits of 27k) [equiv] 0 (mod 27). But perhaps there's a way to check for divisibility by 9 and then by 3, excluding that factor of 9 . . .)

And towr. Sorry, I should have specified: notepad version 5.1   ;)
Title: Re: Notepad calculator
Post by towr on Oct 6th, 2003, 5:12am
Well, it's easy enough to check if it's divisable by 2,4 and several other powers of 2, or several powers of 5, or any power of ten.
But powers of three will take a bit more thinking..
Title: Re: Notepad calculator
Post by Mike_V on Oct 6th, 2003, 5:39am
While I don't think it'll help with this problem, this discussion reminded me of other divisibility stuff.
This post: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1065443701;start=0
I just thought I'd link cause it's related.
Title: Re: Notepad calculator
Post by James Fingas on Oct 6th, 2003, 10:28am

on 10/06/03 at 04:21:03, Mike_V wrote:
The question is then, is there a way to check for multiple divisibilities without actually dividing the number? ie can we use some version of this method to check for divisibility by 27?


The general divisibility tests involve multiplying each digit by a coefficient and then adding them. It would be possible in notepad, but not just using search/replace.
Title: Re: Notepad calculator
Post by BNC on Oct 6th, 2003, 3:26pm

on 10/06/03 at 04:21:03, Mike_V wrote:
ie can we use some version of this method to check for divisibility by 27?


For your example of 27, the best divisibility rule I know is (using 27*37=999) to divide the number into groups of 3 (strating from the right), and adding the groups together. The number is divisible by either 27 or 37 iff the result does. (The process may have to be repeated).
Title: Re: Notepad calculator
Post by NickH on Oct 14th, 2003, 12:52pm
Here's a related puzzle.

With the same rules as the original puzzle, show the following number is composite:

11871419003987228264918498796376974960729607480040
68449946337915761479776150552447513118714190039872
28264918498796376974960729607480040684499463379157
61479776150552447513118714190039872282649184987963
76974960729607480040684499463379157614797761505524
47513118714190039872282649184987963769749607296074
80040684499463379157614797761505524475131187141900
39872282649184987963769749607296074800406844994633
79157614797761505524475131187141900398722826491849
87963769749607296074800406844994633791576147977615
05524475131187141900398722826491849879637697496072
96074800406844994633791576147977615055244751311871
41900398722826491849879637697496072960748004068449
94633791576147977615055244751311871419003987228264
91849879637697496072960748004068449946337915761479
77615055244751311871419003987228264918498796376974
96072960748004068449946337915761479776150552447513
Title: Re: Notepad calculator
Post by Rezyk on Oct 14th, 2003, 11:30pm
Also, how do you use notepad to determine the value of (x mod 11) for any x (that can fit in notepad) in a constant number of steps?

Note: I take advantage of a quirk of notepad that I can't be sure exists in all versions.  (I'm using Version 5.0 Build 2195 SP4)

Hint: The quirk involves [hide]File->Save.[/hide]

My method should also be extendable to any number instead of 11, actually.


on 10/06/03 at 03:22:32, Sir Col wrote:
By the way, welcome to the forum, Rezyk.


Thanks!  I've been a lurker/fan for a while.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board