The p-adic Approach

The Linear System at Hand

n = 40;
b = Table[0, {n}]; 
    b[[1]] = 1;
A = SparseArray[{{i_, i_} -> Prime[i]}, 
                n] + (# + Transpose[#]) &@
          SparseArray[
            Flatten@Table[{i, i + (2^j)} -> 1, {i, n - 1}, {j, 0, 
                  Log[2. , n - i]}], n];

The Iteration: Hensel Lifting

pAdicLinearSolve[A_, b_, p_, k_] := 
        Module[{lud = LUDecomposition[A, Modulus -> p], x, j, 
            r, Δx}, 
          x = LUBackSubstitution[lud, b, Modulus ->  p]; 
          For[j = 1, j < k, j++, 
            r = (b - A . x)/(p^j); Δx = 
              LUBackSubstitution[lud, r, Modulus ->  p]; 
            x = x + (p^j) Δx]; x];

The Rational Number Reconstruction as given in [vzGG99,§5.10]

RationalReconstruction[f_, m_] := 
      Module[{r0 = m, r = f, t0 = 0, t = 1}, 
        While[Abs[r] ≥  (Sqrt[m]), 
t = 
            t0 - Quotient[r0, r] (t0 = t); r = Mod[r0, (r0 = r)]]; 
        (r/t)]

The  Number of Lifting Steps

pAdicExponent[A_, p_] := 
        Ceiling[2 
             Log[p, 2 Product[
                  A[[i, i]], {i, 
                    Length@A}]]];

The Solution

p = 1125899906842597;
k = pAdicExponent[A, p];
x = pAdicLinearSolve[A, b, p, k];
sol2 = 
      RationalReconstruction[x[[1]], 
        (p^k)]