Description of problem:
I expected the python3 core package to have an autogenerated dependency on libpython3.1.so.1.0, which would have been satisfied by the python3-libs subpackage.

However, in our F-13 builds of python3, the python3 core package does not have this dep:
[root@rawhide ~]# rpm -q python3
python3-3.1.1-25.fc13.i686
[root@rawhide ~]# rpm -qR python3
rpmlib(VersionedDependencies) <= 3.0.3-1
rpmlib(PartialHardlinkSets) <= 4.0.4-1
rpmlib(FileDigests) <= 4.6.0-1
rpmlib(PayloadFilesHavePrefix) <= 4.0-1
rpmlib(CompressedFileNames) <= 3.0.4-1
/bin/sh  
/usr/bin/python3.1  
rpmlib(PayloadIsXz) <= 5.2-1

Looking at the build log:
http://kojipkgs.fedoraproject.org/packages/python3/3.1.1/25.fc13/data/logs/i686/build.log

I see this fragment:
--------
Processing files: python3-3.1.1-25.fc13.i686
Executing(%doc): /bin/sh -e /var/tmp/rpm-tmp.BgOxWu
+ umask 022
+ cd /builddir/build/BUILD
+ cd Python-3.1.1
+ DOCDIR=/builddir/build/BUILDROOT/python3-3.1.1-25.fc13.i386/usr/share/doc/python3-3.1.1
+ export DOCDIR
+ rm -rf /builddir/build/BUILDROOT/python3-3.1.1-25.fc13.i386/usr/share/doc/python3-3.1.1
+ /bin/mkdir -p /builddir/build/BUILDROOT/python3-3.1.1-25.fc13.i386/usr/share/doc/python3-3.1.1
+ cp -pr LICENSE README /builddir/build/BUILDROOT/python3-3.1.1-25.fc13.i386/usr/share/doc/python3-3.1.1
+ exit 0
Finding  Provides: /builddir/build/SOURCES/find-provides-without-python-sonames.sh
objdump: /builddir/build/BUILDROOT/python3-3.1.1-25.fc13.i386/usr/lib/python3.1/distutils/command/wininst-9.0-amd64.exe: File format not recognized
Finding  Requires: /usr/lib/rpm/redhat/find-requires
Provides: python(abi) = 3.1
Requires(rpmlib): rpmlib(VersionedDependencies) <= 3.0.3-1 rpmlib(PartialHardlinkSets) <= 4.0.4-1 rpmlib(FileDigests) <= 4.6.0-1 rpmlib(PayloadFilesHavePrefix) <= 4.0-1 rpmlib(CompressedFileNames) <= 3.0.4-1
Requires: /bin/sh /usr/bin/python3.1
--------

Looks like /usr/lib/rpm/redhat/find-requires didn't pick up the requirement of /usr/bin/python3 upon libpython3.1.so.1.0

Note that the specfile has:
Source1: find-provides-without-python-sonames.sh
%global _use_internal_dependency_generator 0
%global __find_provides %{SOURCE1}

so perhaps the old external dep generator isn't working properly.

On a rawhide box, if I run:
  # echo /usr/bin/python* | /usr/lib/rpm/redhat/find-requires
the only output I get is:
  /usr/bin/python2.6

I get no output (am I correctly remembering how to invoke this?); I was expecting it to look at the ELF files, read the NEEDED metadata, and output a "Requires" on those SO-names.

The ELF file does have this data:
[root@rawhide ~]# eu-readelf -d /usr/bin/python3 | grep NEEDED
  NEEDED            Shared library: [libpython3.1.so.1.0]
  NEEDED            Shared library: [libpthread.so.0]
  NEEDED            Shared library: [libdl.so.2]
  NEEDED            Shared library: [libutil.so.1]
  NEEDED            Shared library: [libm.so.6]
  NEEDED            Shared library: [libc.so.6]


On an F-12 box, the script _does_ emit these lines:
[david@F-12 ~]$ echo /usr/bin/python* | /usr/lib/rpm/redhat/find-requires
/usr/bin/python2.6
/usr/bin/python3
/usr/bin/python3.1
libc.so.6
libc.so.6(GLIBC_2.0)
libc.so.6(GLIBC_2.3.4)
libc.so.6(GLIBC_2.4)
libdl.so.2
libm.so.6
libpthread.so.0
libpython2.6.so.1.0
libpython3.1.so.1.0
libutil.so.1

Version-Release number of selected component (if applicable):
Still seen with python3-3.1.1-25.fc13

Not seen on local rebuilds of the SRPM upon my F-12 box, though; these have the requirement.

Additional info:
First seen by Jonathan Dieter when trying to rebuild python-deltarpm with python3 support: bug 555624 showed these build failures:
http://koji.fedoraproject.org/koji/getfile?taskID=1973985&name=build.log
http://koji.fedoraproject.org/koji/getfile?taskID=1973986&name=build.log
which contain this log line:
  /usr/bin/python3.1: error while loading shared libraries: libpython3.1.so.1.0: cannot open shared object file: No such file or directory

Looking at the corresponding "root.log" files for those tasks, I see that the python3 package is installed, but not python3-libs:

Installing:
 bzip2-devel      x86_64    1.0.5-6.fc12                         build    244 k
 popt-devel       x86_64    1.13-6.fc12                          build    324 k
 python-devel     x86_64    2.6.4-18.fc13                        build    160 k
 python3-devel    x86_64    3.1.1-24.fc13                        build    135 k
 rpm-devel        x86_64    4.8.0-9.fc13                         build     86 k
 xz-devel         x86_64    4.999.9-0.1.beta.20091007git.fc13    build     38 k
 zlib-devel       x86_64    1.2.3-23.fc12                        build     39 k
Installing for dependencies:
 expat            x86_64    2.0.1-10.fc13                        build     75 k
 file-devel       x86_64    5.04-3.fc13                          build     22 k
 libffi           x86_64    3.0.9-1.fc13                         build     24 k
 python           x86_64    2.6.4-18.fc13                        build    4.8 M
 python-libs      x86_64    2.6.4-18.fc13                        build    615 k
 python3          x86_64    3.1.1-24.fc13                        build    4.4 M