64 bit - Installing 32 bit libraries on 64 system, libz.so.1 missing

I have tried several alternatives from answers to similar questions (1, 2 and 3) (see also below) to get the libraries I need. It still doesn't work and I get this error message when trying to run my 32-bit software on my 64 bit system (Lubuntu 15.10):

$ ./aiStarter: error while loading shared libraries: libz.so.1: cannot open shared object file: No such file or directory

[1]+  Exit 127                ./aiStarter

So this is what I've tried:

$ sudo dpkg --add-architecture i386

$ sudo apt-get install libstdc++6:i386
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following package was automatically installed and is no longer required:

  libc6-i386
Use 'apt-get autoremove' to remove it.
The following extra packages will be installed:
  gcc-5-base:i386 libc6:i386 libgcc1:i386
Suggested packages:
  glibc-doc:i386 locales:i386
The following NEW packages will be installed:
  gcc-5-base:i386 libc6:i386 libgcc1:i386 libstdc++6:i386
0 upgraded, 4 newly installed, 0 to remove and 1 not upgraded.
Need to get 4 537 kB of archives.

After this operation, 12,0 MB of additional disk space will be used.
Do you want to continue? [Y/n] Y    #Answered yes, etc...

$ sudo apt-get install package:i386
Reading package lists... Done    
Building dependency tree       
Reading state information... Done
E: Unable to locate package package

$ sudo apt-get install build-essential:i386

Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:

 build-essential:i386 : Depends: gcc:i386 (>= 4:5.2) but it is not going to be installed
                    Depends: g++:i386 (>= 4:5.2) but it is not going to be installed
                    Depends: dpkg-dev:i386 (>= 1.17.11)
E: Unable to correct problems, you have held broken packages.

Also tried my hand at finding exactly what package it is I actually need (not sure if it's even the correct way):

$ apt-file update
$ sudo apt-file -x search '/libz.so.1$'

E: The cache is empty. You need to run 'apt-file update' first.

Other ways I should try?