Step 1: Anemos
Antiquated > Normal = 100 Protean Crystals
Normal > +1 = 400 Protean Crystals
+1 > +2 = 800 Protean Crystals
+2 > Anemos = 3 Pazuzu Feathers
Pazuzu Feathers can be obtained through killing Pazuzu, 3 per kill or purchased from the Expedition Birdwatcher for 300 Protean Crystals each.
Total: 1300 (2100) Protean Crystals and 3 Pazuzu Feathers.
Step 2: Pagos
Anemos > Pagos = 5 Frosted Protean Crystals
Pagos > +1 = 500 Pagos Crystals + 10 Frosted Protean Crystals
+1 > Elemental = 5 Louhi's Ice + 16 Frosted Protean Crystals
Frosted Protean Crystals are obtained via gathering "Light" which is available after level 25 once you've completed the level 20 and 23 quests for Krile. Each bar of "Light" can be turned in at the Forge for 1 Frosted Protean Crystal. You can hold up to a maximum of 9 bars of "Light" at one time.
Louhi's Ice is dropped by Louhi, 2 per kill. They can also be purchased from the Expedition Birdwatcher for 50 Pagos Crystals each.
Total: 31 Frosted Protean Crystals, 500 (750) Pagos Crystals and 5 Louhi's Ice.
Step 3: Pyros
Elemental > +1 = 150 Pyros Crystals and 10 unique Logogram actions unlocked
+1 > +2 = 200 Pyros Crystals and 20 unique Logogram actions unlocked
+2 > Pyros = 300 Pyros Crystals, 5 Penthesilea's Flames and 30 unique Logogram actions unlocked
Penthesilea's Flames are dropped by Penthesilea, 3 per kill. They can also be purchased from the Expedition Birdwatcher for 50 Pyros Crystals each.
In addition, farming "Light" will allow you to adjust the stats on your weapon. As a NIN you should be looking for Crit, Direct Hit and Determination.
Total: 650 (900) Pyros Crystals, 5 Penthesilea's Flames and 30 unique Logogram actions.
Step 4: Hydatos
Pyros > Hydatos = 50 Hydatos Crystals
Hydatos > +1 = 100 Hydatos Crystals
+1 > Base Eureka = 100 Hydatos Crystals
Base Eureka > Eureka = 100 Hydatos Crystals + 5 Crystalline Scales
Eureka > Physeos = 100 Eureka Fragments
Crystalline Scales are only found from killing Providence Watcher, 3 per kill.
Eureka Fragments are only found within Baldesion Arsenal.
Total: 350 Hydatos Crystals, 5 Crystalline Scales and 100 Eureka Fragments