My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.

       
#include <iostream>
       
#include <vector>
       
 
       
// find last number standing ... between 1 and n

       
unsigned int bruteForceP(unsigned int n)
       
{
       
  std::vector<unsigned int> numbers;
       
  // fill with 1..limit
       
  for (unsigned int i = 1; i <= n; i++)
       
    numbers.push_back(i);
       
 
       
  bool left2right = true;
       
  while (numbers.size() > 1)
       
  {
       
    std::vector<unsigned int> next;
       
 
       
    // from left to right: keep numbers at odd positions (1,3,5,...), note: zero-based index
       
    // from right to left: if there is an odd amount of numbers, keep odd numbers, else even numbers
       
    size_t i = left2right ? 1 : numbers.size() % 2;
       
    for (; i < numbers.size(); i += 2)
       
      next.push_back(numbers[i]);
       
 
       
    // ... and the other direction in the next iteration
       
    left2right = !left2right;
       
    numbers = std::move(next);
       
  }
       
 
       
  return numbers[0];
       
}
       
 
       
// sum of bruteForceP(1..limit)
       
// solves S(10^5) in a few seconds

       
unsigned int bruteForceS(unsigned int limit)
       
{
       
  unsigned int sum = 0;
       
  for (unsigned int i = 1; i <= limit; i++)
       
    sum += bruteForceP(i);
       
  return sum;
       
}
       
 
       
// there is a pattern:
       
// P(n) = 4 * P(n/4) - 2 if n % 4 = {0,1}
       
// P(n) = 4 * P(n/4)     if n % 4 = {2,3}
       
// and the initial values are P(1) = 1, P(2) = P(3) = 2

       
unsigned long long fastP(unsigned long long n)
       
{
       
  // it's pretty fast to solve P() for small n with brute force
       
  const size_t CacheSize = 20;
       
  static unsigned char cache[CacheSize] = { 0 };
       
  if (n <= CacheSize)
       
  {
       
    // actually I could hard-wire 1 => 1, 2 => 2, 3 => 2, 4 => 2
       
    // but that would render my nice brute-force code useless ;-)
       
    if (cache[n] == 0)
       
      cache[n] = bruteForceP(n);
       
    return cache[n];
       
  }
       
 
       
  auto result   = fastP(n / 4) * 4;
       
  // keep result unchanged if second-to-last bit is set (same as n % 4 >= 2)
       
  return result + (n & 2) - 2; // branch-free code of if (n%4>=2) return result; else return result - 2;
       
}
       
 
       
// right now almost the same code as bruteForceS, but calls fastP instead of bruteForceP and respects the modulo
       
// solves S(10^8) in a few seconds

       
unsigned long long slowS(unsigned long long limit, unsigned int modulo = 987654321)
       
{
       
  unsigned long long sum = 0;
       
  for (unsigned long long i = 1; i <= limit; i++)
       
  {
       
    auto current = fastP(i);
       
    sum += current;
       
    //std::cout << i << ": +" << current << " =" << sum << std::endl;
       
 
       
    // avoid too frequent modulo operations
       
    if (sum > 10 * modulo)
       
      sum %= modulo;
       
  }
       
  return sum % modulo;
       
}
       
 
       
// no idea yet how to accelerate slowS ...

       
unsigned long long fastS(unsigned long long /*limit*/, unsigned int /*modulo = 987654321*/)
       
{
       
  return 0;
       
}
       
 
       
int main()
       
{
       
  unsigned long long limit = 1000000000000000000ULL;
       
  std::cin >> limit;
       
 
       
  // solve examples
       
  //std::cout << bruteForceP(9) << std::endl;
       
  //std::cout << bruteForceS(1000) << std::endl;
       
 
       
  std::cout << slowS(limit) << std::endl;
       
  return 0;
       
}

This solution contains 14 empty lines, 23 comments and 2 preprocessor commands.