A065759_b

[hv at crypt.org]

%N A065759 For a number n of length l, let f(n) be the sum of the products
  of the first i digits of x multiplied by the last l-i digits, for i from
  1 to l-1, e.g. f(1234) = 1*234 + 12*34 + 123*4 = 1134. Sequence gives n
  such that f(n) = n.

I've been looking at the extension of this sequence to arbitrary base b.

In general, we can calculate f_b(n) by summing the contributions of each
digit. A digit d at position b^k will contribute d * b^k * s_k / (b - 1),
where s_k is the sum of the digits to the right of this digit minus the
digits to the left.

Thus taking 655_10 as an example, we get:

  f_10(655) = 1/9 * (600 * (+5+5) + 50 * (+5-6) + 5 * (-6-5))
            = 5895 / 9 = 655

Alternatively, if n has a digit sum of d, we can append a new digit thus:

  f_b(bn + k) = b * f_b(n) + k * (bn - d) / (b - 1)   for 0 <= k < b

so that, given f(65) = 30 and a digit sum of 11:

  f_10(655) = 10 * 30 + 5 * (650 - 11) / 9
            = 300 + 5 * 71 = 655

In the binary case, this simplifies enough to show easily that no
solutions to f_2(n) = n exist: we get f_2(n) < n if n has fewer than
3 "1" digits, f_2(n) > n if it has more than 3 "1"s, and when
n = 2^x + 2^y + 2^z with x > y > z, we have f_2(n) = 2 * (2^x - 2^z)
which can never match.

It is clear that if f_b(n) = n then f_b(n * b^k) = n * b^k for all k > 0.
I therefore looked only for n not divisible by b, and found the following
primitive solutions:

  base 2: none
  base 3: none (>3^17, if any)
  base 4: 58, 117, 165
  base 5: 72
  base 6: 58, 88, 165
  base 7: none (>7^10, if any)
  base 8: 172, 187, 243, 356, 6345, 9929
  base 9: none (>9^9, if any)
  base 10: 655, 1461, 1642, 2361, 3442
  base 11: 356, 576
  base 12: 201, 224, 333, 488, 556, 1086, 1286, 2202
  base 13: 3930, 12042
  base 14: 525, 579, 707, 1125, 1673, 4529, 12173
  base 15: 384, 1224
  base 16: 634, 997, 1237, 2260, 2440, 6515, 18035, 88593, 150033
  base 17: 856, 1944
  base 18: 498, 1416, 3411, 7176, 7687, 13195, 2327982
  base 19: none (>19^8 if any)

Also at least one result for each base 20 .. 266, and some peak first
solutions:
  base 37: 235844
  base 49: 3474702
  base 67: 31984474
  base 93: 72081262
  base 127: 618909616
  base 267: >2 * 10^11 (if any)

These lists are not guaranteed exhaustive, but I let the program check
at least up to a few million times the base in each case. I've also
checked the decimal case up to 10^10.

These results suggest that it should be possible to determine an answer
(probably "no") to the outstanding question in A065759:

%C A065759 Are there any terms > 3442 which are not just a previous term
  followed by zeros?

.. and in general to determine a function of b that represents an upper
bound on primitive solutions.

I think the individual base-dependent lists above are not particularly
interesting as sequences, but more interesting might be the list of
bases for which no solutions exist (2, 3, 7, 9, 19, 267?), the first
solution for each base (0, 0, 58, 72, 58, 172, 0, 655, ...) and the
number of primitive solutions for each base (0, 0, 3, 1, 3, 0, 6, ...).
However it would be unsafe to add any of them without surer evidence
that these results are complete.

At http://www.crypt.org/hv/puzzle/A065759.c you'll find the short C
program I used (1,405 bytes).

Hugo