Number of simple paths in a Tesseract

If you don't know where to post something, put it here and an administrator or moderator will move it to the right place.

Re: Number of simple paths in a Tesseract

Postby zero » Thu Apr 03, 2008 8:18 pm

I now have a lower bound of 54 billion. This could take a while. I'll return when I have something substantially new to report.
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby Mucleus » Fri Apr 04, 2008 5:37 pm

I have listed the 480 paths of length 8 for a tesseract here: http://www.geocities.com/mucleusman/permute.txt

They are all distinct. :\
Mucleus
Mononian
 
Posts: 6
Joined: Fri Mar 28, 2008 7:29 pm

Re: Number of simple paths in a Tesseract

Postby zero » Fri Apr 04, 2008 8:27 pm

Thank you for making that list of 480 paths available. I agree that they are all distinct -- however, some of these sequences do not represent simple paths, and that is why the total number of them is greater than 456. The non-simple paths need to be eliminated to obtain the correct count. As it happens, the 24 non-simple paths are listed under "Type 2." Each line contains a duplicated node:

line number, node visited twice
1, 0011
2, 0011
3, 0101
4, 0110
5, 0101
6, 110
7, 0011
8, 0011
9, 0101
10, 0110
11, 0101
12, 0110
13, 1001
14, 1010
15, 1001
16, 1010
17, 1100
18, 1100
19, 1001
20, 1010
21, 1001
22, 1010
23, 1100
24, 1100

By the way: For n=5, I think my estimated lower bound for the total number of simple paths (from one vertex to the opposite one on an n-cube) may be too high. This is good news, because the smaller the number, the quicker it will be to finish the count. My estimates are all based on the progress of the count thus far, plus an educated guess on what fraction of the possibilities has been covered already. Not a very rigorous process.
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby Mucleus » Sat Apr 05, 2008 12:42 pm

Ah, thank you. I suck :D
Mucleus
Mononian
 
Posts: 6
Joined: Fri Mar 28, 2008 7:29 pm

Re: Number of simple paths in a Tesseract

Postby zero » Sat Apr 05, 2008 4:13 pm

RESULTS!

We all make mistakes. Being able to catch some of them and acknowledge and/or fix the rest is what makes it OK. Also, the way I look at it, the best ones have unexpectedly interesting outcomes.

Or just lucky ones. My estimate for P(5) based on the partial results was much too high. Thus, I already have the final result of running the program to systematically test each possible path. The following numbers are unconfirmed, but I present them with a reasonable degree of confidence in them because of prior testing of the logic used in this calculating procedure. It's the Maple code disclosed earlier made more efficient by eliminating needless duplication of the first two hops. That cuts calculation time by n(n-1).

P(5)=18,651,552,840

Letting the length be the number of hops from the first node to the last, then this number is broken down as follows using the format (length, number of simple paths): (5, 120), (7, 1200), (9, 12840), (11, 131640), (13, 1170480), (15, 8676600), (17, 53824320), (19, 269240520), (21, 1035734160), (23, 2885364240), (25, 5354040960), (27, 5793610320), (29, 2880050400), (31, 369695040)
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby zero » Sat Apr 05, 2008 4:25 pm

Another way to list results that preserves the information about the numbers of simple paths of each length:

P(1)=1!*(1)
P(2)=2!*(1)
P(3)=3!*(1+1+1)
P(4)=4!*(1+4+19+66+110+68)
P(5)=5!*(1+10+107+1097+9754+72305+448536+2243671+8631118+24044702+44617008+48280086+24000420+3080792)
. . . . . . . . . .
P(n)=n!*(1+. . . ?)

This is just begging for generalization.
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby Mucleus » Sat Apr 05, 2008 4:43 pm

Awesome! That will definitely help with finding P(n). Google is very unhelpful sometimes though:
Phonebook results for 1 4 19 66 110 68
Robin Fuller (419) 661-1068 29461 Lime City Rd, Perrysburg, OH 43551 Map

:P

Perhaps the number of simple paths of length n+2 is always n! * (nC3)? I will investigate :) And then there is just lots of work remaining :P

Edit: The formula works for n = 6. Hopefully this is too good to be false
Mucleus
Mononian
 
Posts: 6
Joined: Fri Mar 28, 2008 7:29 pm

Re: Number of simple paths in a Tesseract

Postby Keiji » Sun Apr 06, 2008 11:33 pm

Uhh, guys?

Congratulations and all, but I feel a bit left out here :cry:
User avatar
Keiji
Administrator
 
Posts: 1984
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Number of simple paths in a Tesseract

Postby papernuke » Tue Apr 15, 2008 4:39 am

When youpeople mean "simple paths," What do you mean?
do you man the number of straight 1D paths?
if you started from
(0,0,0,0)
and tried to go to
(1,1,1,1)
wouldn't there only be one linear path?
"Civilization is a race between education and catastrophe."
-H.G. Wells
papernuke
Tetronian
 
Posts: 612
Joined: Sat Jul 08, 2006 6:33 pm
Location: California, US of A

Re: Number of simple paths in a Tesseract

Postby zero » Tue Apr 15, 2008 5:52 am

No, the paths are sequences of jumps between vertices that are connected by an edge. So you have to follow the edges to go anywhere.

The meaning of a "simple path" in the context of graph theory is that no vertex is visited more than once. In modern works, it is typically taken for granted that "path" refers to a "simple path" (or for those that start and end in the same place, "cycle" refers to a "simple cycle"). However, it may still be made explicit for emphasis, and it's important not to make this assumption with older literature.
zero
Trionian
 
Posts: 139
Joined: Wed Nov 07, 2007 5:45 am
Location: Florida

Re: Number of simple paths in a Tesseract

Postby pat » Wed Apr 16, 2008 1:06 pm

zero wrote:P(5)=18,651,552,840


I got a late start on this thread. In fact, I hadn't noticed page 2 of the thread, so I probably started after you had already finished.

My first cut was just brute force, every path, ignoring all symmetries. That plugged away all weekend before I killed it and made it more efficient by a factor of n (n-1) (n-2) and adding progress reports. If your number above is correct, I'm now 1/4-th of the way there in the last ten hours.

The factor of n (n-1) (n-2) comes from going the first three steps each in a new direction, or going the first two steps, taking the third step back in the opposite direction as the first step, then taking the fourth step in a new direction.

Here's my current Lisp code (with the progress reporting eliminated for clarity). The gist is that it keeps the current path in a list with the current position being the first thing in the list. If it's at the target, it returns one. Otherwise, it runs through all possible moves it could make from there, looking for ones that aren't in the current path. It recurses on each and sums the results.
Code: Select all
(defparameter *invertor* (vector 1 0))

(defun count-paths (so-far target)
    (declare (optimize (speed 3) (safety 0)))
    (let ((dims (length (car so-far)))
          (cur  (car so-far)))
        (if (equalp cur target)
            1
            (do ((ii 0 (1+ ii))
                 (sum 0))
                ((= ii dims) sum)
                (let ((next (copy-seq cur)))
                    (setf (elt next ii) (elt *invertor* (elt next ii)))
                    (unless (member next so-far :test #'equalp)
                        (push next so-far)
                        (incf sum (count-paths so-far target))
                        (pop so-far)))))))

(defun cube-vector (nn &rest dirs)
    (let ((ret (make-array nn :initial-element 0)))
        (dolist (dd dirs)
            (setf (elt ret dd) 1))
        ret))

(defun count-paths-in-n-dimensions (nn)
    (let ((c000 (cube-vector nn))
          (goal (make-array nn :initial-element 1)))
        (if (>= nn 3)
            (let ((c000 (cube-vector nn))
                  (c001 (cube-vector nn 0))
                  (c011 (cube-vector nn 0 1))
                  (c010 (cube-vector nn 1))
                  (c110 (cube-vector nn 1 2))
                  (c111 (cube-vector nn 0 1 2)))
                (+
                    (* nn (- nn 1) (- nn 2)
                        (count-paths (list c111 c011 c001 c000) goal))
                    (* nn (- nn 1) (- nn 2)
                        (count-paths (list c110 c010 c011 c001 c000) goal))))
            (count-paths (list c000) goal))))

(do ((ii 1 (1+ ii)))
    ((> ii 5))
    (format t "~a-d = ~a~%" ii (count-paths-in-n-dimensions ii)))
pat
Tetronian
 
Posts: 563
Joined: Tue Dec 02, 2003 5:30 pm
Location: Minneapolis, MN

Re: Number of simple paths in a Tesseract

Postby pat » Fri Apr 18, 2008 12:56 pm

Yep... my code agrees... 18,651,552,840.

But, I'm thinking P(6) is going to require a whole different approach.... maybe even a distributed.net effort.
pat
Tetronian
 
Posts: 563
Joined: Tue Dec 02, 2003 5:30 pm
Location: Minneapolis, MN

Previous

Return to Where Should I Post This?

Who is online

Users browsing this forum: No registered users and 6 guests

cron