Self-referential continued fractions

Rather than trying incessantly to catch up, why not just start with something on top of the pile?

The other day I had a Shower Thought. No idea at the time whether it “was anything” or not. I am sure it’s not novel, and I’m sure if I looked in the right online index with the right search terms it would be 100 years old or so.

Succinctly:

Can a generalized continued fraction (of the sort I’ve talked about before) be constructed, using non-negative numerators and denominators only, so that the decimal representation of the number is as close as possible to the concatenation of the numerators and denominators?

So here’s a counterexample: The (infinite) continued fraction I can represent compactly as \([1;2,3,4,5,6,7,\dots]\), means

But that evaluates to a decimal number that is not 1.234567891011121314..., which is what I want.

So I wrote a stupid little Ruby program (not included here) to do hillclimbing and look for one. I started with a chain of 20 constant integers, thinking “that’s about enough”, and basically just calculated both the concatenated string-to-double number, and the recursively-defined continued fraction value itself.

And then I changed one of the numbers, up or down by ±1 at random, making sure none were ever zero or negative, and just to avoid some weird stuff I thought might be a bug, never more than 999.

Against all expectations, the damned thing did in many cases hillclimb to a pretty good example. For instance, this one: \([10, 10, 59, 36, 1, 2, 51, 67, 1, 1, 45, 54, 1, 4, 42, 43, 3, 1, 66, 56]\), which is

or about \(10.105936125167124\) based on Ruby’s precision. I suppose I could use BigDecimal to get closer maybe.

Anyway, the desired value of the expression is \(10.105936125167114554144243316656\) but that approximation is correct for the first 13 decimal places, and I didn’t actually hillclimb more than a few seconds, so… it seems pretty easy?

I’m startled.

The weird pathology I saw, and which still worries me a bit about my code, is a bit of stumbling around the 0.09 vs 0.11 threshold. I suppose that may be something that falls out after time, but in the moment it felt as though the hillclimbing was just fiddling digits far away from this crucial decimal point.

Still: shower thoughts still fun.

Later

I’ve been poking, wondering about the occasional failures to converge (probably will come back to bite me, at some point). But also wondering about representation problems when using double floating-point values. So I modified my Ruby code (included below) to work with the BigDecimal library, and relaxed some of the assumptions about constant ranges, and found [1, 240, 993, 935, 325, 179, 1274, 1212, 350, 34, 628, 738, 294, 371, 840, 928, 483, 499, 784, 306], which evaluates to

(where I’ve indicated term bouondaries with spaces, and marked the divergence point with an inline circle) a difference of 0.550056763904624808103950022e-27 from the concatenated 58-digit decimal, I am told.

I’m still flying by seat of pants here, with no tests, just exploring. But it’s interesting enough to provoke a little more exploring, I think. For instance, I’ve only hard-coded a 20-constant fraction. What might be possible if I generalized this to a real recursive function of arbitrary length?

And is arithmetic difference the right metric to be minimizing? Maybe I should be doing some kind of digitwise comparison? Count the number of digits that are incorrect, regardless of position? That’s weird, mathematically, but certainly more familiar in an evolutionary algorithms setting.

Are there repeating continued fractions that work this way? I know that any repeated continued fraction is a rational number, and every rational number’s decimal expansion ends in a (possibly trivial) repeated sequence. Can they be brought into congruence this way?

Something for another day.

Have some stupid Ruby code:

require 'bigdecimal'

def to_float(a)
  BigDecimal("1.0") + a[0]/(a[1] +
        a[2]/(a[3] +
        a[4]/(a[5] +
        a[6]/(a[7] +
        a[8]/(a[9] +
        a[10]/(a[11] +
        a[12]/(a[13] +
        a[14]/(a[15] +
        a[16]/(a[17] +
        a[18])))))))))
end

def to_decimal(a)
  return BigDecimal(a.inject("#{1}.") {|string,arg| string + "#{arg.to_i}"})
end

def mutate(a)
  b = a.clone
  idx = rand(b.length)
  if rand() < 0.5 && b[idx] < 99999
    b[idx] += 1
  elsif b[idx] > 1
    b[idx] -= 1
  end
  return b
end

BigDecimal.limit(50) # set the representation limit

args = 19.times.collect {BigDecimal("#{rand(1000)+1.0}")}

# puts args.inspect
# puts mutate(args).inspect

1000000.times do
  variant = mutate(args)
  if (to_float(args) - to_decimal(args)).abs() > (to_float(variant) - to_decimal(variant)).abs()
    args = variant
    puts variant.collect {|d| d.to_i}.inspect
    puts "#{to_float(variant)}, #{to_decimal(variant)}: #{to_float(variant)-to_decimal(variant)}"
  end
end