In Python/pythonrun.c the following definition exists:
static wchar_t *progname = L"python";

This is then used by Py_GetProgramName which is used by calculate_path in Modules/getpath.c 

Since in python 3, the default executable is python3, and not python, when calculate_path searches for "python" it will find where python 2 is installed instead of where python3 is installed.  This is the error message that this causes:

Could not find platform independent libraries <prefix>
Could not find platform dependent libraries <exec_prefix>
Consider setting $PYTHONHOME to <prefix>[:<exec_prefix>]

I recommend that line be changed to:
static wchar_t *progname = L"python3";

since that is the default executable name.

For my purposes (which is making an executable that embedds python 3), I was able to work around this by calling: 
Py_SetProgramName(L"python3");
before
Py_Initialize();

Here is a part of an strace where Python fails to find python3:
(This would work if progname=L"python3" )
...
23249 stat("/opt/python/3.2.2.3/bin/python", 0x7fff2881cbf0) = -1 ENOENT 
(No such file or directory)
23249 readlink("/usr/local/bin/python", "/usr/bin/python", 4096) = 15
23249 readlink("/usr/bin/python", "python2.7", 4096) = 9
23249 readlink("/usr/bin/python2.7", 0x7fff2881bb70, 4096) = -1 EINVAL (Invalid argument)
23249 stat("/usr/bin/Modules/Setup", 0x7fff2881cbf0) = -1 ENOENT (No such file or directory)
23249 stat("/usr/bin/lib/python3.2/os.py", 0x7fff2881cbf0) = -1 ENOENT (No such file or directory)
23249 stat("/usr/bin/lib/python3.2/os.pyc", 0x7fff2881cbf0) = -1 ENOENT (No such file or directory)
23249 stat("/usr/lib/python3.2/os.py", 0x7fff2881cbf0) = -1 ENOENT (No such file or directory)
23249 stat("/usr/lib/python3.2/os.pyc", 0x7fff2881cbf0) = -1 ENOENT (No such file or directory)
23249 stat("/lib/python3.2/os.py", 0x7fff2881cbf0) = -1 ENOENT (No such file or directory)
23249 stat("/lib/python3.2/os.pyc", 0x7fff2881cbf0) = -1 ENOENT (No such file or directory)
23249 write(2, "Could not find platform independ"..., 55) = 55
...
$ which python3
/opt/python/3.2.2.3/bin/python3

Any opposition?

Joshua: what command did you run under strace?

This sounds reasonable. Is there any reason that this change might be detrimental?

Maybe it would be better to use L"python3.2" for Python 3.2 and L"python3.3" for Python 3.3.

> Joshua: what command did you run under strace?

A program I created that embeds python3.  I could create a minimum piece of code that triggered the bug if needed.

> Maybe it would be better to use L"python3.2" for Python 3.2 and L"python3.3" for Python 3.3.

L"python3.2" and L"python3.3" would work better than the current L"python" since calculate_path assumes that progname is the name of an actual executable for python 3.  It only sorta works now with L"python" if python 2 and python 3 are installed in the same location, which was not the case for me since python 2 came with the system and python 3 was a local install.

Hmm, actually, there is a potential problem. While "python3" is the official binary under POSIX, under Windows it is "python" (well, "python.exe").

Joshua, if you are embedding Python, why don't you simply call Py_SetPath to set the search path appropriately? Or is it not enough? (I've lost memory of the mazy details of how we calculate paths :-S).

> Joshua, if you are embedding Python, why don't you simply call Py_SetPath to set the search path appropriately? Or is it not enough? (I've lost memory of the mazy details of how we calculate paths :-S).

Setting Py_SetPath manually would basically require me to replicate the work done in Modules/getpath.c to figure out where the python libraries are.  I already set PYTHONPATH to get it to find my own modules.  (Note that there is a big difference between setting PYTHONPATH the environmental variable and calling Py_SetPath, Py_SetPath assumes that you are setting the python library module paths as well.)

The basic problem is that in function calculate_path (inside of Modules/getpath.c ) it has the following code:

char *_path = getenv("PATH");
...
wchar_t *prog = Py_GetProgramName();
...
 while (1) {
...
            joinpath(progpath, prog);
            if (isxfile(progpath))
                break;
...

which goes through the path and tries to find an executable with the same name as returned by Py_GetProgramName()

So if I do a """Py_SetProgramName(L"python3");""" that method works because prog="python3" but if I don't then the method fails because prog="python".  

Basically, to fix this bug, somehow, "wchar_t *prog =" in calculate_path needs to get the actual python executable for this version of python.

Okay, that's convincing enough. Besides, I don't think it has ever worked for Windows, since it misses the adding of a ".exe" suffix.

New changeset c97d78415f5a by Antoine Pitrou in branch '3.2':
Issue #15020: The program name used to search for Python's path is now "python3" under Unix, not "python".
http://hg.python.org/cpython/rev/c97d78415f5a

New changeset 61e6ac40c816 by Antoine Pitrou in branch 'default':
Issue #15020: The program name used to search for Python's path is now python3 under Unix, not python.
http://hg.python.org/cpython/rev/61e6ac40c816

This should be fixed now. Thanks!