All your base palindromic belong to us

Question

Generate the sequence number of bases in which n is a palindrome (OEIS A126071).

Specifically, the sequence is defined as follows: given a number n, express it in base a for a = 1,2, ..., n, and count how many of those expressions are palindromic. "Palindromic" is understood in terms of reversing the base-a digits of the expression as atomic units (thanks, @Martin Büttner). As an example, consider n= 5:

a=1: the expression is 11111: palindromic
a=2: the expression is 101: palindromic
a=3: the expression is 12: not palindromic
a=4: the expression is 11: palindromic
a=5: the expression is 10: not palindromic

Therefore the result for n=5 is 3. Note that OEIS uses bases 2, ..., n+1 instead of 1, ..., n (thanks, @beaker). It's equivalent, because the expressions in base 1 and n+1 are always palindromic.

The first values of the sequence are

 1, 1, 2, 2, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 4, 4, 4, 2, 4, 5, ...

Input is a positive integer n. Output is the first n terms of the sequence.

The program should theoretically work (given enough time and memory) for any n up to limitations caused by your default data type in any internal computations.

All functions allowed. Lowest number of bytes wins.

If it's helpful to anyone, it's worth noting that a number n is also always palindromic in base n-1. — Computronium, Aug 31, 2017 at 13:43

Community · Accepted Answer · 2020-06-17 09:04:33Z

9

Pyth, 13 bytes

mlf_ITjLdSdSQ

The brevity of this is mostly due to the Invaluable "Invariant" command.

msf_ITjLdSdSQ       implicit: Q=input
m         d         map lambda d over
           SQ       Inclusive range 1 to Q
      jLdSd         Convert d to all the bases between 1 and d
  f                  filter lambda T:
   _IT                 is invariant under reverse
 l                  number that are invariant under reverse

If True is an acceptable output for 1, msm_IjdkSdSQ (12 bytes) works.

Try it here.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 19, 2016 at 22:24

lirtosiast

21.4k5 gold badges50 silver badges126 bronze badges

2

\$\begingroup\$ See FryAmTheEggman's suggestion to use _I# rather than f_IT (I'm not 100% sure it was available, but it seems to have been). \$\endgroup\$
– Jonathan Allan
Aug 31, 2017 at 19:02

Add a comment |

emanresu A · Accepted Answer · 2022-09-04 06:32:40Z

Jelly, 12 bytes

bRµ=UP€S
RÇ€

Try it online!

An old 14-byte version (The Jelly interpreter had a bug that made converting to unary impossible)

bR‘$µ=UP€S
RÇ€

Try it online!

How it works

bR‘$µ=UP€S  Helper link. Argument: z

 R‘$        Apply range and increment, i.e., map z to [2, ..., z + 1].
            In the non-competing version R simply maps z to [1, ... z].
b           Convert z to each of the bases to the right.
    µ       Begin a new, monadic chain. Argument: base conversions
     =U     Compare the digits of each base with the reversed digits.
            = has depth 0, so [1,2,3]=[1,3,3] yields [1,0,1].
       P€   Take the product of the innermost arrays.
         S  Sum all resulting Booleans.


RÇ€         Main link. Argument: n

R           Yield [1, ..., n].
 Ç€         Apply the helper link to each.

Community · Accepted Answer · 2020-06-17 09:04:33Z

MATL, 19 20 bytes

:"0@XK:Q"K@:YAtP=A+

Uses current release (10.1.0), which is earlier than this challenge.

Try it online!

Explanation

:            % vector [1,2,...,N], where "N" is implicit input
"            % for each number in that vector
  0          % push 0
  @          % push number 1,2,...N corresponding to current iteration, say "n" 
  XK         % copy n to clipboard
  :Q         % vector [2,3,...,n+1]
  "          % for each number "m" in that vector
    K        % push n
    @:       % vector [1,2,...,m]
    YA       % express n in base m with symbols 1,2,...,m
    tP       % duplicate and permute
    =A       % 1 if all entries are equal (palindrome), 0 otherwise
    +        % add that number
             % implicitly close the two loops and display stack contents

Martin Ender · Accepted Answer · 2016-01-20 17:57:56Z

2

CJam, 20 bytes

ri{)_,f{)b_W%=}1bp}/

Test it here.

edited Jan 20, 2016 at 17:57

answered Jan 19, 2016 at 22:32

Martin Ender

196k65 gold badges443 silver badges966 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

Python 2, 97 bytes

c=1;n=int(input())
for b in range(2,n):
	a=[];z=n
	while z:a+=[z%b];z//=b
	c+=a[::-1]==a
print c

My first Python post, actually my first Python code at all
probably has some golfing potential.

Try it online!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 31, 2017 at 20:18

Titus

14.6k1 gold badge23 silver badges41 bronze badges

Add a comment |

Damien · Accepted Answer · 2016-01-20 12:29:01Z

1

Haskell, 88 bytes

a!b|a<b=[a]|1>0=mod a b:(div a b)!b
f n=[1+sum[1|x<-[2..y],y!x==reverse(y!x)]|y<-[1..n]]

answered Jan 20, 2016 at 12:29

Damien

2,4478 silver badges20 bronze badges

Add a comment |

Neil · Accepted Answer · 2016-01-20 15:51:13Z

1

ES6, 149 bytes

n=>[...Array(n)].map((_,i)=>[...Array(i)].reduce((c,_,j)=>c+(''+(a=q(i+1,j+2,[]))==''+a.reverse()),1),q=(n,b,d)=>n<b?[n,...d]:q(n/b|0,b,[n%b,...d]))

Works for bases > 36 too.

edited Jan 20, 2016 at 15:51

answered Jan 20, 2016 at 15:45

Neil

163k12 gold badges69 silver badges271 bronze badges

Add a comment |

user81655 · Accepted Answer · 2016-01-25 14:22:41Z

JavaScript (ES6), 105 95 bytes

f=(n,b)=>b?b<2?1:f(n,b-1)+([...s=n.toString(b)].reverse().join``==s):n<2?[1]:[...f(n-1),f(n,n)]

Explanation

Takes a number from 1 to 36 (the limitation of base conversion in JavaScript) and returns an array of the sequence.

Recursive function that checks for palindromes when a base is passed, else returns the sequence if just n is passed.

f=(n,b)=>

  // Base palindrome checking
  b?
    b<3?1:                 // return 1 for base-1, since toString(2)
    f(n,b-1)+(             // return the sum of all lower bases and check  this
      [...s=n.toString(b)] // s = n in base b
      .reverse().join``==s // add 1 if it is a palindrome
    )

  // Sequence generation
  :
    n<2?[1]:               // return 1 for the first value of the sequence
    [...f(n-1),f(n,n)]     // return the value for n after the previous values

Test

var solution = f=(n,b)=>b?b<2?1:f(n,b-1)+([...s=n.toString(b)].reverse().join``==s):n<2?[1]:[...f(n-1),f(n,n)]

<input type="number" oninput="result.textContent=solution(+this.value)" />
<pre id="result"></pre>

Is there a way to turn that into a recursive function? I feel like that could save some bytes. — Mama Fun Roll, Jan 24, 2016 at 6:05

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

PHP, 73+1 bytes

while(++$i<$argn)$c+=strrev($n=base_convert($argn,10,$i+1))==$n;echo$c+1;

works for bases 1 to 36. Run as pipe with -nR or try it online.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 31, 2017 at 18:47

Titus

14.6k1 gold badge23 silver badges41 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

PHP, 92+1 bytes:

for($b=$c=1;$b++<$n=$argn;$c+=$a==array_reverse($a))for($a=[];~~$n;$n/=$b)$a[]=$n%$b;echo$c;

works for all bases. Run as pipe with -nR or try it online.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 31, 2017 at 18:48

Titus

14.6k1 gold badge23 silver badges41 bronze badges

Add a comment |

Sasha · Accepted Answer · 2017-09-03 21:58:17Z

1

><>, 197+2 Bytes

+2 for -v flag

:1+0v    ;n\
1\  \$:@2(?/
:<~$/?)}:{:*}}@:{{
\   \~0${:}
>$:@1(?\::4[:&r&r]:$&@@&%:&@&$@-$,5[1+{]$~{{:@}}$@,$
~~1 \  \
?\~0>$:@2(?\$1-:@3+[}]4[}1-]=
 \  /@@r/!?/
r@+1/)0:<
  /?/$-1$~<
~$/       \-1

tio.run doesn't seem to return any output for n>1, but you can verify it on https://fishlanguage.com. Input goes in the "Initial stack" box.

answered Sep 3, 2017 at 21:58

Sasha

4713 silver badges7 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Japt, 10 bytes

õ_õ!ìZ èêS

Try it

Explanation

õ              :Range [1,input]
 _             :Map each Z
  õ            :  Range [1,Z] (let's call each X)
   !ìZ         :   Convert Z to a base X digit array
       è       :  Count
        êS     :   Palindromes

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 30, 2018 at 13:04

Shaggy

41.3k4 gold badges34 silver badges91 bronze badges

1

\$\begingroup\$ õ_õ hahaha nice emoji \$\endgroup\$
– Luis felipe De jesus Munoz
Aug 30, 2018 at 13:05

Add a comment |

Triggernometry · Accepted Answer · 2019-01-02 20:11:13Z

Python 2, 85 bytes

def f(a):b,c=2,0;exec'd,m=[],a\nwhile m:d+=[m%b];m/=b\nc+=d[::-1]==d;b+=1;'*a;print c

Try it online!

Expects an integer as an argument.

Explanation:

# named function
def f(a):
    # initialize variable to track base (b) and to track palindromes (c)
    b,c=2,0
        # construct code
        '
        # initialize variable to store remainders (m) and to track divisor (d)
        m,d=[],a
        # while d is not zero,
        # add the current remainder to the array
        # and divide d by the base and assign the result back to d
        while d:m+=[m%b];d/=b
        # False == 0 and True == 1, so add 1 to total if m == reversed(m)
        c+=m[::-1]==m;
        # increment base
        # terminate with ; so that next statement can be executed separately
        b+=1;
        '
    # execute constructed statement (a) times
    exec'....................................................'*a
    # print result
    print c

Razetime · Accepted Answer · 2020-10-29 13:42:37Z

1

Husk, 13 bytes

mλṁoS=↔`B¹ḣ)ḣ

Try it online!

not sure if I can avoid using a lambda here.

answered Oct 29, 2020 at 13:42

Razetime

26.8k3 gold badges26 silver badges71 bronze badges

Add a comment |

emanresu A · Accepted Answer · 2022-09-04 07:01:40Z

1

Jelly, 8 bytes

bRfU$Lµ€

Try it online!

Alternatively:

bRŒḂ€Sµ€

Try it online!

edited Sep 4, 2022 at 7:01

emanresu A

34.5k5 gold badges81 silver badges189 bronze badges

answered Aug 31, 2017 at 8:42

Erik the Outgolfer

40.4k5 gold badges41 silver badges121 bronze badges

Add a comment |

Stack Exchange Network

All your base palindromic belong to us

15 Answers 15

Pyth, 13 bytes

Jelly, 12 bytes

How it works

MATL, 19 20 bytes

Explanation

CJam, 20 bytes

Python 2, 97 bytes

Haskell, 88 bytes

ES6, 149 bytes

JavaScript (ES6), 105 95 bytes

Explanation

Test

PHP, 73+1 bytes

PHP, 92+1 bytes:

><>, 197+2 Bytes

Japt, 10 bytes

Explanation

Python 2, 85 bytes

Husk, 13 bytes

Jelly, 8 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
base-conversion
palindrome
or ask your own question.

Linked

Hot Network Questions

All your base palindromic belong to us

15 Answers 15

Pyth, 13 bytes

Jelly, 12 bytes

How it works

MATL, 19 20 bytes

Explanation

CJam, 20 bytes

Python 2, 97 bytes

Haskell, 88 bytes

ES6, 149 bytes

JavaScript (ES6), 105 95 bytes

Explanation

Test

PHP, 73+1 bytes

PHP, 92+1 bytes:

><>, 197+2 Bytes

Japt, 10 bytes

Explanation

Python 2, 85 bytes

Husk, 13 bytes

Jelly, 8 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
base-conversion
palindrome
or ask your own question.