Re: [math-fun] walking every road in a city - math-fun Digest, Vol 202, Issue 28
One method to walk every road in a city, especially if, like a postman you must walk both sides of every street, is to treat the road network as an electrical network with unit resistors in each street , then designating one street as the battery, calculate the currents and voltages using node analysis. If the voltage is chosen as the number of spanning trees in the network, the currents and voltages should come out as integers. The network of streets then becomes a squared rectangle in the squared rectangle theory of Brooks, Stone, Smith and Tutte. To walk both sides of every street exactly once, starting at an outside corner of the rectangle, walk the diagonal to the opposite corner of that square, then at the T-intersection 'bounce' at 45 degrees like a reflected laser beam into the adjacent square, heading for it's opposite corner, and so on. The diagonal walk will eventually exit at one of the other corners. Then enter at one of the other unused corners and diagonally walk until you exit the final corner. It may happen that these two walks exhaust all the squares, and hence traverse all the streets in both directions, but it may not, there may be intranversed squares. If there are, enter one the intraversed squares at the boundary of the rectangle, and diagonal walk from there until you return to where you started that particular walk. Keep doing this until all squares are traversed. Some complications, the network may have bridges and overpasses so it is not planar. Partition the network into planar and K5 or K2-3 components and traverse those separately. One way streets and dead ends shouldn't be a problem as the can be taken out of the network and added back to the network later. Another complication is that I stead of a T-intersection in the interior of the squares rectangle you may encounter a cross, in which you need to decide a convention on which way to turn at the corner.
Message: 4 Date: Tue, 17 Dec 2019 22:30:17 -0500 (EST) From: "Keith F. Lynch" <kfl@KeithLynch.net> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] Walking every road in a city Message-ID: <47d0rT2pbFz1ZVx@panix2.panix.com>
With a map in hand and an app on his phone, Jarad Schofer is taking the concept of a jog through the city to a whole new level: He plans to run every road and alley in the District.
"You know I've lived here a long time and I kind of thought I'd run everywhere and now I can see that's really nowhere near the case," he said.
He's a teacher with a doctorate in mathematics and only recently got into running. He started with 5Ks, then moved to 10K races.
Now with a few big races under his belt, Schofer has knocked out 860 miles on his mission to tackle the streets of D.C. In all, he intends to run around 2,500 miles.
. . .
He said the biggest challenge has been overlapping certain streets but according to his calculations, it's impossible to avoid.
https://wtop.com/dc/2019/12/dc-runner-is-on-a-mission-to-cover-every-inch-of...
What's the best algorithm for walking (or running) every road in a city while minimizing duplication?
Only a small part of DC is on a regular grid. Mostly its road network is pretty much random.
------------------------------
Message: 5 Date: Tue, 17 Dec 2019 23:21:13 -0500 From: Neil Sloane <njasloane@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Boustrophedon primes Message-ID: < CAAOnSgTeWCo3smnjuCWL94xwj-TYX+z0Qi_1+f63rzUiKrhQYQ@mail.gmail.com> Content-Type: text/plain; charset="UTF-8"
Allan, I had exactly the same idea, and this afternoon I created A330545! It is indeed the key to the whole problem - and of course the recurrence makes it a lot easier to compute.
On Tue, Dec 17, 2019 at 5:27 PM Allan Wechsler <acwacw@gmail.com> wrote:
There is an underlying sequence, which tells what columns successive prime numbers land in. This is the alternating sum of the decremented first differences of the primes, with the sequence starting at 2. Just reading off Eric's picture, I get
2,2,3,2,5,4,7,6,9,4,5,0,3,2,5,0,....
A330339 is then the primes indexed by occurrences of zero in this alternating sum.
On Tue, Dec 17, 2019 at 5:14 PM Neil Sloane <njasloane@gmail.com> wrote:
On Tue, Dec 17, 2019 at 4:24 PM ?ric Angelini <eric.angelini@skynet.be
wrote:
Thank you Walter! This is an incentive for ski slopes! Best, ?.
Le 17 d?c. 2019 ? 20:05, Walter Trump <w@trump.de> a ?crit :
The next Boustrophedon primes are 3821 and 3989. Here is a continuation of Eric's arrangement of numbers (you cannot read the digits, they are too small): https//www.trump.de/Boustrophedon-Primes.png
Walter
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
------------------------------
Subject: Digest Footer
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
------------------------------
End of math-fun Digest, Vol 202, Issue 28 *****************************************
Hmm I think I'm wrong about one-way streets using the diagonal walk method. They would need to be traversed twice. If each street needs to be traversed only once, isn't this the Chinese postman problem? On Wed, Dec 18, 2019, 16:04 Stuart Anderson <stuart.errol.anderson@gmail.com> wrote:
One method to walk every road in a city, especially if, like a postman you must walk both sides of every street, is to treat the road network as an electrical network with unit resistors in each street , then designating one street as the battery, calculate the currents and voltages using node analysis. If the voltage is chosen as the number of spanning trees in the network, the currents and voltages should come out as integers. The network of streets then becomes a squared rectangle in the squared rectangle theory of Brooks, Stone, Smith and Tutte. To walk both sides of every street exactly once, starting at an outside corner of the rectangle, walk the diagonal to the opposite corner of that square, then at the T-intersection 'bounce' at 45 degrees like a reflected laser beam into the adjacent square, heading for it's opposite corner, and so on. The diagonal walk will eventually exit at one of the other corners. Then enter at one of the other unused corners and diagonally walk until you exit the final corner. It may happen that these two walks exhaust all the squares, and hence traverse all the streets in both directions, but it may not, there may be intranversed squares. If there are, enter one the intraversed squares at the boundary of the rectangle, and diagonal walk from there until you return to where you started that particular walk. Keep doing this until all squares are traversed. Some complications, the network may have bridges and overpasses so it is not planar. Partition the network into planar and K5 or K2-3 components and traverse those separately. One way streets and dead ends shouldn't be a problem as the can be taken out of the network and added back to the network later. Another complication is that I stead of a T-intersection in the interior of the squares rectangle you may encounter a cross, in which you need to decide a convention on which way to turn at the corner.
Message: 4 Date: Tue, 17 Dec 2019 22:30:17 -0500 (EST) From: "Keith F. Lynch" <kfl@KeithLynch.net> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] Walking every road in a city Message-ID: <47d0rT2pbFz1ZVx@panix2.panix.com>
With a map in hand and an app on his phone, Jarad Schofer is taking the concept of a jog through the city to a whole new level: He plans to run every road and alley in the District.
"You know I've lived here a long time and I kind of thought I'd run everywhere and now I can see that's really nowhere near the case," he said.
He's a teacher with a doctorate in mathematics and only recently got into running. He started with 5Ks, then moved to 10K races.
Now with a few big races under his belt, Schofer has knocked out 860 miles on his mission to tackle the streets of D.C. In all, he intends to run around 2,500 miles.
. . .
He said the biggest challenge has been overlapping certain streets but according to his calculations, it's impossible to avoid.
https://wtop.com/dc/2019/12/dc-runner-is-on-a-mission-to-cover-every-inch-of...
What's the best algorithm for walking (or running) every road in a city while minimizing duplication?
Only a small part of DC is on a regular grid. Mostly its road network is pretty much random.
------------------------------
Message: 5 Date: Tue, 17 Dec 2019 23:21:13 -0500 From: Neil Sloane <njasloane@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Boustrophedon primes Message-ID: < CAAOnSgTeWCo3smnjuCWL94xwj-TYX+z0Qi_1+f63rzUiKrhQYQ@mail.gmail.com> Content-Type: text/plain; charset="UTF-8"
Allan, I had exactly the same idea, and this afternoon I created A330545! It is indeed the key to the whole problem - and of course the recurrence makes it a lot easier to compute.
On Tue, Dec 17, 2019 at 5:27 PM Allan Wechsler <acwacw@gmail.com> wrote:
There is an underlying sequence, which tells what columns successive prime numbers land in. This is the alternating sum of the decremented first differences of the primes, with the sequence starting at 2. Just reading off Eric's picture, I get
2,2,3,2,5,4,7,6,9,4,5,0,3,2,5,0,....
A330339 is then the primes indexed by occurrences of zero in this alternating sum.
On Tue, Dec 17, 2019 at 5:14 PM Neil Sloane <njasloane@gmail.com> wrote:
On Tue, Dec 17, 2019 at 4:24 PM ?ric Angelini < eric.angelini@skynet.be> wrote:
Thank you Walter! This is an incentive for ski slopes! Best, ?.
Le 17 d?c. 2019 ? 20:05, Walter Trump <w@trump.de> a ?crit :
The next Boustrophedon primes are 3821 and 3989. Here is a continuation of Eric's arrangement of numbers (you cannot read the digits, they are too small): https//www.trump.de/Boustrophedon-Primes.png
Walter
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
------------------------------
Subject: Digest Footer
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
------------------------------
End of math-fun Digest, Vol 202, Issue 28 *****************************************
participants (1)
-
Stuart Anderson