14
\$\begingroup\$

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.)

\$\endgroup\$
  • \$\begingroup\$ Sorry, little confusion between me and Zach on the question. Everything should be formatted right now. \$\endgroup\$ – a spaghetto Sep 24 '15 at 22:17
  • \$\begingroup\$ A useful observation: in a confidant number, each digit is one plus double the previous digit, except the second digit is instead one plus the first digit. \$\endgroup\$ – xnor Sep 24 '15 at 23:14
  • \$\begingroup\$ Going columnwise reveals another (possibly) useful pattern ;) \$\endgroup\$ – Geobits Sep 25 '15 at 0:41
  • 1
    \$\begingroup\$ In the example, why is CD not in the list? Since all other combinations where the second digit is one more than the first digit are listed, I don't understand why CD does not qualify. \$\endgroup\$ – Reto Koradi Sep 25 '15 at 4:50
  • \$\begingroup\$ That was an accident :P Fixed, thanks for pointing it out. \$\endgroup\$ – a spaghetto Sep 25 '15 at 13:26
2
\$\begingroup\$

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
\$\endgroup\$
9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Wow, dang. Nearly half the size compared to Python 3! Hmm. I wonder how many bytes I can save if I use some of your tricks... \$\endgroup\$ – El'endia Starman Sep 24 '15 at 23:48
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can save one byte by changing your last line to print('\n'.join(''.join(map(lambda x:[str(x),chr(x+55),chr(x+61)][(x>9)+(x>35)],x))for x in X)). Also, currently it's 201 bytes; not 200. \$\endgroup\$ – Zach Gates Sep 24 '15 at 23:40
  • \$\begingroup\$ @ZachGates: I did think of that, but didn't realize I could leave out the brackets. Thanks! \$\endgroup\$ – El'endia Starman Sep 24 '15 at 23:43
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Oh man, this is awesome. I've been trying to learn GS2 but I've been having a real rough time with it :P \$\endgroup\$ – a spaghetto Oct 2 '15 at 1:25
3
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.