Code advice for a neat math q

marmaris · October 8, 2010, 11:53pm

Gentlemen; I started learning javascript a week ago or so and wanted to tackle this math question that I remembered from many many moons back:

There is a math contest held in a city and 1 to 10 people are joining from 67 cities. So a min of 67 and a max of 670 people. Each contestant was given a number in order of their entrance into the contest hall. After the results are announced, they ask the champion what his entrance number to the hall was, and he replies: “The sum of the people entering before me and the sum of the people entering after me are equal. See if you can find my number?”

Really neat question, for me anyways.

It took me a while to write this code and it worked. But I’m sure it could be written in a much nicer/tidier fashion.

Pls advise. Thank you kindly.

for (i=40; i<=500; i++)
{
var p = ((i-1)*i)/2

	for (x=1; x&lt;=100; x++)
	{
	if ((((i+x)*(i+(x+1))/2)-i-p)==p)
	alert(i)
	if ((((i+x)*(i+(x+1))/2)-i-p)&gt;p)
	break;
	}

}

p.s. I chose to start from 40 and end at 500 after a quick calculation (rounded the numbers) cause less than 40 and more than 500 would not be possible. Or so me thinks.

mrhoo · October 13, 2010, 4:11am

You can do something similar to get the total number of entrants
that satisfies the problem-

next total= current total*6 - previous total+2;
The first ten results match with brute-force
testing each number, but I haven’t got a proof to rely on the pattern holding up forever.

Nice puzzle!

function guesswho(){
	var A= [1, 6], B= [1, 8], C= ['1. 6 of 8'], 
        y= 8, x= 6, limit= Math.pow(2, 51), i=2;
	while(x && y){
		x= A[A.length-1]*6- A[A.length-2];
		if(x<limit) A.push(x);
		else x= null;
		y= B[B.length-1]*6- B[B.length-2]+2;
		if(y<limit){
			B.push(y);
			C.push((i++)+'. '+x+' of '+y);
		}
		else y= null;
	}
	return C;
}

//guesswho().join(’
');

/* returned value: (String)

6 of 8
35 of 49
204 of 288
1189 of 1681
6930 of 9800
40391 of 57121
235416 of 332928
1372105 of 1940449
7997214 of 11309768
46611179 of 65918161
271669860 of 384199200
1583407981 of 2239277041
9228778026 of 13051463048
53789260175 of 76069501249
313506783024 of 443365544448
1827251437969 of 2584123765441
10650001844790 of 15061377048200
62072759630771 of 87784138523761
361786555939836 of 511643454094368
*/

You should also be able to check the first 7-10 results from this, depending on the browser:

function whichEntrant(max, min){
	min= min || 5;
	var out= [], after, next, before= 0, n= 1;
	while(n+1< min) before+= n++;
	after= next= n+1;
	while(n< max){
		before+= n++;
		after-= n;
		while(after< before && next< max){
                        after+= ++next;
		}
		if(after== before){
                        out[out.length]= n+' of '+next;
		}
		if(after< before || n>46611179) n= max;
	}
	return out;
}

// whichEntrant(1000000)// try more or less 0s

Beyond 10 you need to use a repeating method that does a bite at a time,
and you need BigIntegers-
the sums get beyond javascript’s integer precision at 2^51,which is the sum of something
less than the first ninety million digits…

So lets find the proof instead…

marmaris · October 12, 2010, 8:21pm

I just realized the relationship between those numbers:
1, 6, 35, 204, 1189, 6930, 40391

(x 6 - the previous number) as in
(6 x 6 -1) = 35
(35 x 6 - 6) = 204
(204 x 6 - 35) = 1189
(1189 x 6 - 204) = 6930
(6930 x 6 - 1189) = 40391
so the next number should be:
(40391 x 6 - 6930) = 235416

WOW! This would also make an interesting number pattern question.

system · October 10, 2010, 12:01am

I only get that pop up prompt in IE and not in any of the other browsers (FF, Opera, Chrome and Safari)

I think IE senses you’re doing a lot of “number crunching” and so asks if you want to continue or not. I just keep clicking 'No" (to the question to stop running the script) 3-4 times and eventually the 204 answer pops up.

mrhoo · October 9, 2010, 10:49pm

The next year, each of the 67 cities sent between 10 to 100 athletes,
and the same champion gave the same answer.

This time, he was number 1189 of 1681 contestants.

But the next year, when the number of entries increased tenfold again,
they could not tell if he was number 6930 of 9800 or 40391 of 57121,
so they gave the prize to the first runner up,
and the old champion swore off addition forever.

Yet another method, this one quits calculating as soon as the followers total less than the preceders:

function whichEntrant(max, min){
    min= min || 1;
    var B= [], before= 0, after, next, n= 1;
    while(n< max){
        before+= n++;
        after= next= n+1;
        if(n>= min){
            while(after<before && next< max){
                after+= ++next;
            }
            if(after== before){
               B.push('Number '+n+' of '+next+' entrants');
            }
            if(after<before) break;
        }
    }
    if(B.length)return 'The entrant is '+ B.join(' or\
');
    else return 'You need more entrants to solve this.';
}

alert(whichEntrant(670, 67));
// The entrant is Number 204 of 288 entrants.

marmaris · October 9, 2010, 10:44pm

Hi Kalon; I seem to be getting an error: “Stop running Javascript?” message when I copy/pasted all your code. I wonder if I’m doing sth wrong? Does it run fine for you?

marmaris · October 9, 2010, 1:32am

sorry I wasn’t very clear maybe but the sum in this case is: 1+2+3+4+5. For ex. if he was the 100th person to go into the hall then that would mean 1+2+3+4+5+…99 has to equal 101+102+103+104+…n.

mrhoo · October 14, 2010, 6:07pm

// Its hard to leave this alone.

function runnersNumber(min, max){
	var limit= Math.pow(2, 51);
	min= min && min> 0? min: 6;
	max= max && max<limit? max: limit;

	var runner= 1, total= 1, prev, 
        numbers= [0, runner], solution= [];

	while(total< max){
		if(runner>= min){
                    solution.push(runner+' of '+total);
	        }
		prev=numbers[1];	
		runner= runner*6- numbers[0];
		total+= runner+prev;
		numbers= [prev, runner];
	}
	return solution;
}

// alert(runnersNumber(67,670));

to return the first 19 (excluding a race with one runner,
which also satisfies the riddle)


if([].map){
	runnersNumber().map(function(itm, i){
		return i+1+'.\	'+itm
	}).join('\
');
	}
	else runnersNumber().join('\
');

mrhoo · October 13, 2010, 3:16pm

I’d like to replace my last post- I nearly forgot the original riddle.

I still haven’t proved it, but this should work:

function guesswho(min, max){
	min= min || 6;
	max= max || Math.pow(2, 51);
	var who= [1, 6], total= [1, 8], x= 6, y= 8,
	C= min> 6? []: ['6 of 8'];

	while(y){
		y= total[1]*6- total[0]+2;
		if(y<max){
			x= who[1]*6- who[0];
			who= [who[1], x];
			total= [total[1], y];
			if(x>= min) C.push(x+' of '+y);
		}
		else y= null;
	}
	return C;
}

/*
test 1: ‘The champion is number ‘+ guesswho(67, 670)+’ entrants.’

return: The champion is number 204 of 288 entrants.
*/

/*
test 2:
'Solutions:
‘+
guesswho().map(function(itm, i){return i+1+’.\ ‘+itm}).join(’
');
return:

Solutions:

1.	6 of 8
2.	35 of 49
3.	204 of 288
4.	1189 of 1681
5.	6930 of 9800
6.	40391 of 57121
7.	235416 of 332928
8.	1372105 of 1940449
9.	7997214 of 11309768
10.	46611179 of 65918161
11.	271669860 of 384199200
12.	1583407981 of 2239277041
13.	9228778026 of 13051463048
14.	53789260175 of 76069501249
15.	313506783024 of 443365544448
16.	1827251437969 of 2584123765441
17.	10650001844790 of 15061377048200
18.	62072759630771 of 87784138523761
19.	361786555939836 of 511643454094368

*/

mrhoo · October 13, 2010, 11:17pm

Another interesting pattern is that the sum of the last
champion’s number and the total entrants added to the current champion’s
number equals the current total entrants.


function guesswho(min, max){
	min= min || 6;
	max= max || Math.pow(2, 51);
	var x= 6, y= 8, numbers= [1, x, y], solution= [];

	while(y<max){
		if(x>= min) solution.push(x+' of '+y);
		x= numbers[1]*6- numbers[0];
		y= x+numbers[1]+numbers[2];
		numbers= [numbers[1], x, y];
	}
	return solution;
}

system · October 9, 2010, 3:27am

ok, nice brain teaser :agree:

I did it this way and both your code and mine give the same answer.

The champion’s number is 204 and the before and after sums = 20706

Your code is less lines though.

 
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title></title>
<script type="text/javascript">
 
window.onload=function() {
var sumBefore = 0;
var sumAfter = 0;
 
for (var totPpl=67; totPpl <= 670; totPpl++) {
 for(var i=1; i <= totPpl; i++) {
    sumBefore = 0;
    sumAfter = 0;
 
     //add up all the before numbers
        for(var j=0; j < i; j++) {
         sumBefore += j;
        }
 
        //add up all the after numbers
        for(var j=i+1; j <= totPpl; j++) {
         sumAfter += j;
        }
 
        if(sumBefore == sumAfter) {
         alert('i = '+i+"\
\
sumBefore and sumAfter = "+sumBefore);
            totPpl = 671; //end processing
            i = totPpl;
        }
    }
} //end of main for loop
 
alert('end');
}
 
</script>
</head>
<body>
</body>
</html>

marmaris · October 12, 2010, 8:08pm

Kalon and mrhoo; thank you so much for the effort. I can run both codes with success. By changing the min max values or totPpl value can arrive at 6, 35, 204 and 1189 which are all similar type of numbers.

mrhoo, I cannot get at the higher numbers you mentioned as I get a javascript terminate alert.

However I am not at a level to follow the logic in the code through.

Is there a way to see what the code is doing step by step; that might help me understand what the code is doing on each line on every loop etc.
I am presently using the free HTML Kit on Windows platform and can’t seem to find such a feature in it.

Any suggestions?

system · October 9, 2010, 12:14am

By “the sum of the people” I assume you mean the sum of the number of people.

In that case for the champion to have had the same number entering before him/her as the number entering afterwards then the total number of people entering must be an odd number.

Therefore isn’t the champion’s entrance number simply


((number of total people - 1) / 2) + 1

So if you had 101 people entering, the champions number would have been 51 with numbers 1-50 (50 people) entering before him/her and numbers 52 -101 (50 people) entering after him/her.

Or have I misunderstood something?

Paul_Wilkins · November 13, 2010, 12:09am

Here’s how I worked it out:

The sum from 1 to 10 can be calculated by adding successive terms from the end of the list

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10

(1 + 10) + (2 + 9) + (3 + 8) + (4 + 7) + (5 + 6)

The formula for this is:
(1 + 10) * 5

Or more generalised:
(start + end) * (end - start + 1) / 2

Now for the question.

“The sum of the people entering before me and the sum of the people entering after me are equal. See if you can find my number?”

Where 67 >= total <= 670

c = champion’s position
t = total people

The sum of people before
(start + end) * (end - start + 1) / 2
or
(1 + c - 1) * (c - 1 - 1 + 1) / 2
or
c * (c - 1) / 2

The sum of people after
(start + end) * (end - start + 1) / 2
or
(c + 1 + t) * (t - (c + 1) + 1) / 2
or
(c + 1 + t) * (t - c) / 2

So now we have two unknowns, and two equations
c(c - 1) / 2 = (c + 1 + t) * (t - c) / 2
or
t(t + c + 1)/2 - c(c + 1 + t)/2 - c(c - 1) / 2 = 0
or
t(t + c + 1) - c(c + 1 /2
or
t(t + 1) - c(2c) = 0
or
t^2 + t - 2c^2 = 0

So, we’re looking for when
t^2 + t = 2c^2

c^2 = (t^2 + t) / 2
t^2 = 2c^2 - t

So, we can check for when
sqrt(t^2 + t) / 2) is a whole number


var champ, i;
for (i = 67; i <= 670; i += 1) {
    champ = Math.sqrt((i * i + i) / 2);
    if (champ === Math.floor(champ)) {
        alert('Champion: ' + champ + ', Total: ' + i);
    }
}

mrhoo · November 13, 2010, 3:13am

I found you can go one magnitude higher than I was trying with normal javascript integers.

function runnersNumber(min, max){
	var limit= Math.pow(2, 53)-1;
	min= min && min> 0? min: 6;
	max= max && max<limit? max: limit;

	var runner= 1, total= 1, prev, 
        numbers= [0, runner], solution= [];

	while(total< max){
		if(runner>= min){
                    solution.push(runner+' of '+total);
	        }
		prev=numbers[1];	
		runner= runner*6- numbers[0];
		total+= runner+prev;
		numbers= [prev, runner];
	}
	return solution;
}
alert(runnersNumber().join('\
'))

/*  returned value: (String)
6 of 8
35 of 49
204 of 288
1189 of 1681
6930 of 9800
40391 of 57121
235416 of 332928
1372105 of 1940449
7997214 of 11309768
46611179 of 65918161
271669860 of 384199200
1583407981 of 2239277041
9228778026 of 13051463048
53789260175 of 76069501249
313506783024 of 443365544448
1827251437969 of 2584123765441
10650001844790 of 15061377048200
62072759630771 of 87784138523761
361786555939836 of 511643454094368
2108646576008245 of 2982076586042449
*/

system · November 13, 2010, 3:18am

Off Topic:

hmmmmmmm…interesting :scratch:

I wonder if the “powers-that-be” could set up a “Brain Teaser” forum where we could have a separate thread for each brain teaser someone would like to post.

Paul_Wilkins · November 13, 2010, 11:35am

It appears that the sequence is one of triangular numbers that are also square.

A square with sides that are 1189, has the same area as a triangle with sides of 1681.
http://www.whatabeginning.com/BBooks/LangtonLegacy/P.htm

They all relate to root 2

8/6 = 49/35 = 288/204 = 1189 / 1681