All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Spirit of '76 (Posted on 2004-03-14) Difficulty: 3 of 5
Can you find a 76-digit multiple of 276, written exclusively with 7s and 6s?

  Submitted by Federico Kereki    
Rating: 4.2500 (8 votes)
Solution: (Hide)
Let's rather prove, by induction, that for every n there exists a n-digit number multiple of 2^n, written only with sixes and sevens.Let's call such a number M(n). Obviously, M(1)=6. [You could also start with M(0)=0, but it's less clear.] We'll prove that if M(n)/2^n is even, then M(n+1) equals M(n) with a 6 appended at the left, and when M(n)/2^n is odd, then M(n+1) equals M(n) with a 7 at the left.

First case: M(n)/2^n=2K. M(n+1)= 6x10^n+M(n)= 6x10^n+2Kx2^n, which is a multiple of 2^(n+1).

Second case: M(n)/2^n=2K+1. M(n+1)= 7x10^n+M(n)= 7x10^n+2Kx2^n+2^n= 7x5^nx2^n+Kx2^(n+1)+2^n= (7x5^n+1)x2^n+Kx2^(n+1), which also is a multiple of 2^(n+1); note that the first term in parenthesis comes out to be even.

Thus, we've proved that M(n) exists for all n>0. It's also easy to prove that M(n) is unique, realizing that if you take out the leftmost digit, you are left with a possible M(n-1), and so all the way down to M(1), which is certainly unique. The following Python program does the needed calculations:

while i<76:
	if ((m/(2L**i))%2==0):
		m = m + 6 * 10L ** i
		m = m + 7 * 10L ** i
	i = i + 1
print m
This program produces:


Comments: ( You must be logged in to post comments.)
  Subject Author Date
answerK Sengupta2007-05-12 13:48:11
Some ThoughtsLook, Ma, no multiplying!e.g.2004-03-14 20:33:49
calculations provided by ...Charlie2004-03-14 13:59:50
Some Thoughtsmaybe?Tristan2004-03-14 13:51:27
SolutionAnswerNick Hobson2004-03-14 13:48:27
Solutionmore thoughts (actually solution--spoiler)Charlie2004-03-14 13:48:25
HINTS, maybeRichard2004-03-14 12:40:41
Some ThoughtsthoughtsCharlie2004-03-14 12:16:18
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information