Confidant Numbers

Question

Confidant Numbers

Let x be an integer of an arbitrary base, such that D is an array of its digits. x is a Confidant Number if, for all n between 1 and the length of D:

D[n+1] = D[n] + D[n-1] + ... + D[1] + n

---

Take, for example, the number 349 in base 10. If we label the indices for this number, we have the following.

Index    Digit
-----    -----
1        3
2        4
3        9

Starting from the first digit, we have 1 + 3 = 4, which yields the next digit. Then with the second digit we have 3 + 4 + 2 = 9, which, again, yields the next digit. Thus, this number is a Confidant Number.

---

Given an integer with a base between 1 and 62, calculate all the Confidant Numbers for that base, and output a list of them, separated by newlines. You can assume that there is a finite amount of Confidant Numbers for a given base.

For digits greater than 9, use the alpha characters A-Z, and for digits greater than Z use the alpha characters a-z. You will not have to worry about digits beyond z.

They do not have to be output in any particular order.

---

Sample Input:

16

Sample Output:

0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
12
23
34
45
56
67
78
89
9A
AB
BC
CD
DE
EF
125
237
349
45B
56D
67F
125B
237F

This is code golf, so the shortest code wins. Good luck!

(Thanks to Zach for helping out with the formatting and pointing out a few problems.)

Answer 1

Python 2, 104 bytes

n=input()
for i in range(n):
 s=''
 while i<n:s+=chr(48+i+(i>9)*7+i/36*6);print s;i+=n**0**i+i*(s>s[:1])

This uses the following observation: in a confidant number, the digit i is followed by 2*i+1, except it's i+1 instead for the second digit. By trying all possible first digits and adding more digits until they get too big, we can generate all confidant numbers.

We compute the character corresponding the number i as chr(48+i+(i>9)*7+i/36*6), which shifts it into the number, uppercase letter, or uppercase letter range for the intervals 0-9, 10-35, 36-61.

Then, we increase i via i+=i+1 with two adjustments. To make this instead i+=1 after the first digit, we add i conditional on s having more than 1 chars. Also, we need to avoid numbers starting with 0 from being printed, while at the same time allowing 0. To do this, we do a hack that causes i=0 to fail the condition i<n on the next loop by adding n to it. This is done by replacing 1 with n**0**i, which right-associates to n**(0**i), which equals n**(i==0) or n if i==0 else 1.

Answer 2

Python 3, 201 200 bytes

n=int(input())
X=[[i]for i in range(1,n)]
for x in X:
 y=sum(x)+len(x)
 if y<n:X.append(x+[y])
X=[[0]]+X
print('\n'.join(''.join(map(lambda x:[str(x),chr(x+55),chr(x+61)][(x>9)+(x>35)],x))for x in X))

Explanation

The key insight here is that given a sequence x (like, say, [1,2,5]), you can get the next term in the sequence with sum(x)+len(x), which gives 11 in this case (B). Check to see if this is less than n, and if it is, add the extended sequence to the list of all such sequences (seeded by all single digits).

[str(x),chr(x+55),chr(x+61)][(x>9)+(x>35)]

This is how I map sequence items to characters. These are ''.joined together and then printed, separated by newlines.

Answer 3

GS2, 44 bytes

26 c8 2f 08 4d 08 40 64 45 2e 30 42 67 40 24 d0
75 d3 20 e1 35 09 cb 20 23 78 22 09 34 30 e0 32
08 86 84 30 85 30 92 58 09 34 10

It produces the numbers in a different order, but the problem description doesn't specify, so I'm going for it! Here's the output for input of 16.

1
12
125
125B
2
23
237
237F
3
34
349
4
45
45B
5
56
56D
6
67
67F
7
78
8
89
9
9A
A
AB
B
BC
C
CD
D
DE
E
EF
F
0

Here are the mnemonic equivalents for the bytes:

read-num dec save-a
range1
{
    itemize
    {
        dup 
        sum
        over length
        add

        swap right-cons

        dup last push-a le

            push-d eval
        block2 when
    }
    save-d eval
    init inits tail
} map

+ ' fold 

{
    ascii-digits
    uppercase-alphabet catenate
    lowercase-alphabet catenate
    select 
    show-line
} map

0

Answer 4

CJam, 46 42 40 bytes

ri:R,{Q{+_A,s'[,_el^+f=oNo__,+:+_R<}g&}*

Try it online in the CJam interpreter.

How it works

ri:R            e# Read an integer from STDIN and save it in R.
,               e# Push [0 ... R-1].
{               e# Fold; For each element but the first:
                e#   Push the element.
  Q             e#   Push an empty array (accumulator for base-R digits).
  {             e#   Do:
    +           e#     Concatenate the integer and the array on the stack.
    _           e#     Push a copy of the result.
    A,s'[,_el^+ e#     Push "0...0A...Za...z".
                e#     See: http://codegolf.stackexchange.com/a/54348
    f=          e#     Replace each base-R digit with the corresponding character.
    oNo         e#     Print the resulting string and a linefeed.
    _           e#     Push another copy of the accumulator.
    _,+         e#     Append its length to it.
    :+          e#     Add all digits (including the length).
    _R<         e#     Push a copy of the result and compare it with R.
  }g            e#   If the sum is less than R, it is a valid base-R digit,
                e#   the comparison pushes 1, and the loop is repeated.
  &             e#   Intersect the accumulator with an integer that is greater
                e#   or equal to R. This pushes an empty array.
}*              e#

At the end 0 and a few empty arrays are left on the stack, so the interpreter prints 0.

Answer 5

Pyth, 38 bytes

0jms@L+s`MT+rG1Gdf<eTQsm.u+N+lNsNQ]dSQ

Try it online: Demonstration

Explanation:

0jms@L+s`MT+rG1Gdf<eTQsm.u+N+lNsNQ]dSQ  implicit: Q = input base
0                                       print 0
                       m            SQ  map each d of [1, 2, ..., Q] to:
                        .u       Q]d      start with N=[d], apply v Q times
                          +N+lNsN           add (len(N) + sum(N)) to N
                                          gives all intermediate results
                      s                 join to one list of candidates
                 f<eTQ                  filter those, where every digit < Q
  ms@L+s`MT+rG1Gd                       convert numbers to letters 0-9A-Za-z
 j                                      print each on separate line

Answer 6

gawk, 111 bytes

{for(n=$0;n>c=++i;)for(j=0;n>$++j=c+=j;print"")for(c=k=0;k++<j;c+=$k)printf"%c",$k+($k>9?$k>35?61:55:48)}$0="0"

For every starting digit from 1 to base-1 it calculates the next digits, and while these are lower than the base we still have a confidant number. Calculating the next digit while printing. Finally prints 0.