text:
Decompose a number!
Your task is to decompose a number using the format below.
This is similar to base conversion, except that instead of listing the digits in the base, you list the values, such that the list adds up to the input.
If the given base is \$n\$, then each number in the list must be in the form of \$k\times n^m\$, where \$0\le k<n\$ and \$m\$ is unique throughout the list.
Specs

Any reasonable input/output format. Your program/function takes 2 inputs and outputs a list.
Output list can be in any order.
0 can be excluded or included.
Leading 0s are allowed.
Built-ins are allowed.

Testcases
number base   converted list
input1 input2 output
123456 10     [100000,20000,3000,400,50,6] or [6,50,400,3000,20000,100000]
11     2      [8,2,1] or [0,0,0,0,8,0,2,1]
727    20     [400,320,7]
101    10     [100,1] or [100,0,1]

Scoring
This is code-golf. Shortest solution in bytes wins.

Jelly, 7 bytes
lr0⁹*×b

Try it online! or verify all test cases.
How it works
lr0⁹*×b  Main link. Arguments: x (integer), n (base)

l        Compute the logarithm of x to base n.
 r0      Range; yield all non-negative integers less than the logarithm, in
         decreasing order.
   ⁹*    Elevate n to all integers in that range.
      b  Yield the list of base-n digits of x.
     ×   Multiply each digit by the corresponding power of n.

Ah, reversed range...

It is so impressive what can be achieved with so few characters

JavaScript (ES6), 47 bytes

f=(n,b,p=1,q=b*p)=>[...n<q?[]:f(n,b,q),n%q-n%p]
document.write("<pre>"+
[ [ 123456, 10 ], [ 11, 2 ], [ 727, 20 ], [ 101, 10 ] ]
.map(c=>c+" => "+f(...c)).join`\n`)

Care to include a snippet? :)

Pyth - 12 11 bytes
Just a FGITW, can be shorter.
.e*b^Qk_jEQ

Test Suite.

Remove the _ for a byte :)

@KennyLau meant FGITW, it means "Fastest Gun In The West", a phenomenon where people answering first get more upvotes than the better answers.

@KennyLau oh that's allowed, derp.

Jelly, 12 bytes
bLR’*@€U
b×ç

Can be waaaay shorter...
Try it online!

http://jelly.tryitonline.net/#code=YkzhuotAw5dcVcOXYjo&input=&args=MTIzMDU2+MTA

lḞr0⁴*×b should work.

Technically, 0r⁴*³%I works as well.

Scratch that. lr0⁴*×b has the same byte count, without all the extra zeroes.

@Dennis That's definitely different enough to post as a separate answer.

OK, done.

J, 20 19 bytes
[(]*(^<:@#\.))#.inv

Usage
   f =: [(]*(^<:@#\.))#.inv
   10 f 123456
100000 20000 3000 400 50 6
   2 f 11
8 0 2 1
   20 f 727
400 320 7
   10 f 101
100 0 1

Explanation
[(]*(^<:@#\.))#.inv
              #.      Given a base and list of digits in that base,
                      converts it to an integer in base 10
                inv   Power conjunction by -1, creates an inverse
                      Now, this becomes a verb that given a base and an integer in base 10,
                      creates a list of digits in that base representing it
[                     Select the base and pass it along
         #\.          Tally each suffix of the list of base digits,
                      Counts down from n to 1
      <:              Decrements each value
        @             More specifically, decrement is composed with the tally and applied
                      together on each suffix
     ^                Raises each value x using base^x
  ]                   Selects the list of base digits
   *                  Multiply elementwise between each base power and base digit

CJam, 16 bytes
{1$b\1$,,f#W%.*}

An unnamed block that expects the base and the number on top of the stack (in that order) and replaces them with the digit list (including internal zeros, without leading zeros).
Test it here.
Explanation
1$  e# Copy base b.
b   e# Compute base-b digits of input number.
\   e# Swap digit list with other copy of b.
1$  e# Copy digit list.
,   e# Get number of digits M.
,   e# Turn into range [0 1 ... M-1].
f#  e# Map b^() over this range, computing all necessary powers of b.
W%  e# Reverse the list of powers.
.*  e# Multiply each digit by the corresponding power.

TSQL, 68 bytes
DECLARE @ INT=123456,@z INT=10
DECLARE @l INT=1WHILE
@>0BEGIN PRINT @%@z*@l SELECT @/=@z,@l*=@z END

Mathematica, 46 bytes
DiagonalMatrix@IntegerDigits@##~FromDigits~#2&

Explanation:

In[1]:= IntegerDigits[123456,10]

Out[1]= {1, 2, 3, 4, 5, 6}

In[2]:= DiagonalMatrix@IntegerDigits[123456,10] // MatrixForm

Out[2]//MatrixForm= 1   0   0   0   0   0

                    0   2   0   0   0   0

                    0   0   3   0   0   0

                    0   0   0   4   0   0

                    0   0   0   0   5   0

                    0   0   0   0   0   6

In[3]:= DiagonalMatrix@IntegerDigits[123456,10]~FromDigits~10

Out[3]= {100000, 20000, 3000, 400, 50, 6}

Very unexpected use of DiagonalMatrix.  Kindly explain how it works in this case.

Mathematica, 12 bytes
I wonder whether Wolfram Research created this function after seeing the OP's challenge!
NumberExpand

This was introduced in version 11.0 (August, 2016).

Jelly, 8 bytes
bḅ²×¥@b×

Try it online!
²×¥@ seems too long for what it does. I hope there is a shorter way.
Explanation
b             Convert A (the input number) to base B (the input base).
 ḅ²×¥@        Convert from base A×B²
      b×      Convert to base A×B

Regex (ECMAScript), 76 bytes
(?=.*,(x(x*)))(?=.*?(((?=(?=\1*,)(x(x*))(?=\5*,)(?=\2+,)(\2\6*),)\7)*x),)\3+

Takes its input in unary, as the length of two string of xs delimited by a , (number first, then base). Returns its result as the list of matches (each is also a string of xs whose length is the value).
Try it online!
It's a good thing the challenge allows 0 to be excluded or included, because this solution excludes it, and it would not be possible to include it! (The only way to include it would be either to use .NET with the result returned via a capture's stack, or PCRE with a callout.)
The division algorithm is explained in my Division and remainder post.
# If this is the first match, tail = N = input number. Otherwise
# tail = N = current intermediate value, which is the input number
# after having the previous return values all subtracted from it.
(?=
    .*,(x(x*))             # \1 = number base; \2 = \1 - 1
)
(?=
    .*?                    # Decrease tail by the minimum necessary to satisfy
                           # the following assertion:
    # Assert tail is a power of \1; \3 = tail = the largest power of \1 that is
    # less than or equal to N.
    (                      # \3 = tail
        (
            (?=
                # Calculate \5 = tail / \1
                (?=\1*,)   # Assert tail is divisible by \1
                (x(x*))    # \5 = quotient - find the largest that matches the
                           #      following assertions; \6 = \5-1; tail -= \5
                (?=\5*,)   # assert tail is divisible by quotient
                (?=\2+,)   # assert tail is positive and divisible by divisor-1
                (\2\6*),   # assert tail-(divisor-1) is divisible by quotient-1;
                           # \7 = tool to make tail = \5
            )\7            # tail = \5
        )*                 # Iterate the above as many times as possible
        x                  # tail -= 1
    )
    ,                      # Assert tail == 0
)
\3+                        # Return value = M = tail - (tail % \3); tail -= M

Python 2, 44 bytes
lambda n,b:[n/b**i%b*b**i for i in range(n)]

Outputs from least significant to most, with many extra zeroes.
To output most significant to least:
f=lambda n,b,c=1:n*[1]and f(n/b,b,c*b)+[n%b*c]

Recurse, repeatedly taking digits off of n with divmod while scaling up the place value multiplier c.

For the second version, can't you do range(-n,1) instead of range(n,-1,-1)?

@EʀɪᴋᴛʜᴇGᴏʟғᴇʀ Thanks, I didn't see that going in reverse was an option. It even suffices to just do range(n).

Ruby, 35 34 bytes
This is a port of xnor's Python answer, but it prints n times so the test case 727 20 prints 7, 320, 400, and 724 0s. Golfing suggestions welcome.
Edit: 1 byte thanks to Jordan.
->n,b{n.times{|i|p n/b**i%b*b**i}}

You can save a byte with n.times{|i|p ...}.

Pip, 13 bytes
Wa-:Pa%oo*:b

Doing it the old-fashioned way turned out to be shorter than using the TB base-conversion operator. The code runs a while loop until a (the number) is 0. At each iteration, it prints a%o and subtracts it from a. o is preinitialized to 1 and gets multiplied by b (the base) each iteration. (This approach keeps all 0s and also adds a leading 0.)
Try it online!

Vyxal r, 7 bytes
τ:ẏṘ⁰e*

Try it Online!
A nice little answer. Takes value then base
Explained
τ:ẏṘ⁰e*
τ       # Convert value from base 10 to input base
 :ẏṘ    # Duplicate that and push the range [len(that) - 1, 0]
    ⁰e  # Raise base to the power of each item in that
      * # Multiply that by the list of digits of the converted value

JavaScript (V8), 44 bytes
b=>g=n=>n?[...g(~~(n/b)).map(i=>i*b),n%b]:[]

Try it online!
Takes curried input in the form function(base)(number).

Desmos, 57 bytes
k=b^{[floor(log_b(n+0^n))...0]}
f(n,b)=mod(floor(n/k),b)k

Try It On Desmos!
Try It On Desmos! - Prettified

BQN, 18 bytes
-⟜»⊢|˜⊣⋆1+·↕∘⌈⊣⋆⁼+

Tacit function; takes the base as left argument and the number as right argument. Try it at BQN online!
Explanation
Call the left argument b and the right argument n.
-⟜»⊢|˜⊣⋆1+·↕∘⌈⊣⋆⁼+
                ⋆⁼   Inverse exponential (i.e. logarithm)
               ⊣     with base b
                  +  of b + n
              ⌈       Round up to nearest integer
                     This number is at least as large as the number of base-b digits n has
            ↕∘       Range (0-based, exclusive)
         1+·         Add 1 to each
       ⊣⋆            Raise b to each of those exponents
    ⊢|˜              Take n mod each of those powers of b
   »                 Shift a copy of that list right, prepending a 0
-⟜                  and subtract it from the unshifted list

For example, with a base of 3 and a number of 17, we have
+       20
⊣⋆⁼     2.726833027860842
1+·↕∘⌈   ⟨ 1 2 3 ⟩
⊣⋆      ⟨ 3 9 27 ⟩
⊢|˜     ⟨ 2 8 17 ⟩
»       ⟨ 0 2 8 ⟩
-⟜     ⟨ 2 6 9 ⟩

Racket, 82 bytes
(define(d n b[a'()])(if(< n 1)a(d(/ n b)b(cons(*(modulo(floor n)b)(length a))a))))

I'm a winner (!)

So many spaces... does <n 1 not work? (I don't know Racket at all)

No that wouldn't work -- identifiers are delimited only by whitespace, parentheses/braces/curly braces, and some other symbols, like '. It's a good question, though.

(And < is just a variable with a function bound to it)

JavaScript (ES7), 68 bytes
n=>b=>(c=[...n.toString(b)]).map(d=>b**--p*parseInt(d,b),p=c.length)

Test
Test uses Math.pow for browser compatibility.

f=n=>b=>(c=[...n.toString(b)]).map(d=>Math.pow(b,--p)*parseInt(d,b),p=c.length)
document.write("<pre>"+
[ [ 123456, 10 ], [ 11, 2 ], [ 727, 20 ], [ 101, 10 ] ]
.map(c=>c+" => "+f(c[0])(c[1])).join`\n`)

** isn't a valid JavaScript operator though right?

@ericw31415 It's the ES7 exponentiation operator.

Oh, it's experimental. That's why my browser does not support it.

JavaScript, 75 bytes
(a,b)=>[...a.toString(b)].reverse().map(($,_)=>Math.pow(b,_)*parseInt($,b))

Just for fun :)
It could be golfed more, but I'm not too sure how.
ES7, 66 bytes
If ES7 is allowed then:
(a,b)=>[...a.toString(b)].reverse().map(($,_)=>b**_*parseInt($,b))

O, 17 bytes
jQb`S/l{#Qn^*p}d

Two notes:

The third test case does not work due to a bug with base conversion. See phase/o#68.

This does not work in the online interpreter. b hadn't been implemented yet.

><>, 28 bytes
:&\
&*>:{:}$%:n$}-:0=?;ao$&:

Expects the input values to be present on the stack at program start.
As ><> doesn't have list objects, the output is presented as a newline-separated list of values, with the 'units' on the first line. An example run:
Input:
11 2

Ouput:
1
2
0
8

@OP, if this isn't an acceptable output format, let me know and I'll edit the answer accordingly.

PHP, 55 bytes
Uses Windows-1252 encoding.
for($n=$argv[1];$d+$n-=$d=$n%$argv[2]**++$i;)echo$d,~Ó;

Run like this (-d added for aesthetics only):
php -d error_reporting=30709 -r 'for($n=$argv[1];$d+$n-=$d=$n%$argv[2]**++$i;)echo$d,~Ó; echo"\n";' 123056 10

C#, 77 bytes
IEnumerable _(int n,int b){int m=1;while(n>0){yield return n%b*m;n/=b;m*=b;}}

Actually, 17 bytes
;a¡;lrR(♀ⁿ@♂≈♀*;░

Try it online!
Explanation:
;a¡;lrR(♀ⁿ@♂≈♀*;░
                   initial stack: [b n] (b = base, n = number)
;                  dupe b
 a                 invert stack
  ¡                n as a base-b integer
   ;lrR            dupe, length, range, reverse
       (♀ⁿ         raise b to each power in range
          @♂≈      create list of integers from base-b string
             ♀*    pairwise multiplication
               ;░  filter out zeroes

Surely there is a way to avoid ♀? (Golfed off four bytes)

C++, 82 Bytes
int*f(int n,int b){int*a,o[n]{b,n%b};for(a=o+1;*a=(n-=*a++)%(b*=*o););return o+1;}

The main loop is pretty trivial (keep taking modulos and subtracting the lower part). The main savings come from doing lots of calculations in-place and the loop condition being the actual assigned value (which will eventually become 0, after all meaningful output is written to the array)
I haven't been able to figure out why, but ideone throws a runtime error if I try to have the function return o instead of o+1, so I use the extra index to store the powers of b.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Build a word generator!
Your task is to create a program/function to replicate this word generator.
Details
Your program/function take two input. One input is the categories. The other input is the syllable types.
Categories
categories will consist of classes of letters.
For example, V=aeiou means that the letters a, e, i, o, and u will be classified under the category V.

Each category will have a 1-letter name in UPPERCASE.
The letters it contains will all be in lowercase.

Syllable types
For example CV would mean that the syllable will consist of a letter in category C and then a letter in category V.
For example, if C=bcd and V=ae, then the syllable can be ba, be, ca, ce, da, or de.
Your task
Your task is to generate 100 random words, each with a random length of 1-5 syllables, each chosen randomly in the syllable types, with the letter in each category chosen also randomly.
Specs

Any reasonable input/output format. I don't care how you input the list.
All inputs will be valid.

Scoring
This is code-golf. Shortest solution in bytes wins.
Testcase
input1          input2    output
"C=st;V=aeiou"  "CV/CVC"  tasiti tese tossi tesis titi sese saset su sosastesisat sisosis sissa sata to sisas sese satetot sisuta tatote sa tetsesuti sossut ti seso tese tostutsasussi tutiset sasates tasa ta sa satso tastitta tetti sesita setetat tatsi tisetot sassu sessiso satessase sas ses totasta si tetsit titse sase totas sa ta sasesa tasa sostat sesi sissa tato tos tate sustosussatta sustas sassatote tesas sutat tatetatossos testisot tatta tissisisa sasese sesatus tito sisa satas sasisi so sasatustu sosses tetsa tese sestit sestu tisot sutastot sesu tet sotte sisute setotitsesi tita

@Maltysen Thanks, added.

@R.Kap "1-5 syllables, each chosen randomly in the syllable types"

Does the output have to be 100 unique words?

@R.Kap No. Random doesn't mean unique.

Ruby, 80 bytes
gotta go fast
Input is a dictionary hash (for example, {'C' => ['b', 'c'], 'V' => ['a', 'e']}) and a list of syllable structures (for example, ['CV', 'VC'] or %w{CV VC}.
->c,s{100.times{puts (0..rand(5)).map{s.sample}.join.gsub(/./){|e|c[e].sample}}}

For sample input:
c = {
    'C' => %w{r s t l n},
    'V' => %w{a e i o u}
}
s = %w{CV CVC}

This produces a sample output:
salsun
lonlutunonnus
solitlaton
rusitar
lotol
ris
relussetsa
tanotte
nasun
sur
lusin
tuslu
nerunol
sorrelussenu
ni
nanro
nulila
ritlalatiso
nururlontensa
lilas
tatsisuto
lel
rerlisletnut
ler
netlo
sorora
surot
tilsasotisi
rilnolrati
lasrare
totni
surreratlaral
li
tullatilro
rusenoreto
lulnunen
nortille
tut
sanitare
soniserloras
tiritrattitsis
ratretrate
tesne
lastinsolta
sinirsitur
lulesuleno
li
sirurata
nutesnisitur
rulunna
natneretasi
lonre
les
laruletan
nitis
tarletu
tonrora
la
senru
seltotoniles
teransotutel
re
lulsirnilletus
nunanurlon
nunlortotsonna
nolun
tolso
nas
leltirninara
neltinlesla
lulutsisot
lesulusutnis
nolu
nun
tituntillini
ralteres
sasnirosse
tutorlari
nonlelletottan
lirsetutit
so
le
setse
susritterlilu
lorrirotri
linuritlilrat
rernilnelnutel
sulolletrolo
nisatellilru
tulene
tetnan
lisotoslersor
nerlani
ne
tunoletso
nonlontaroltun
rirrostarset
sotlonsiro
net
sutona

No sample output? :(

@KennyLau All right, if you insist...

You know words, you have the best words.

Pyth - 18 bytes
Takes input as a dict and then one structure per line.
V100ssmmO@QkO.zhO5

Try it online here.

Python 3, 117 bytes
(Also works in Python 2.)
lambda C,T:[J(J(R(C[t])for t in R(T))for j in[0]*randint(1,5))for i in[0]*100]
from random import*
R=choice
J="".join

The lambda function takes the categories C as a dictionary and the syllable types T as a list of strings. It returns a list of 100 words. Try it online!
Ungolfed
import random

def wordlist(categories, types):
    return [
        "".join(
            "".join(
                random.choice(categories[t])
                for t in random.choice(types))
            for j in range(random.randint(1, 5)))
        for i in range(100)]

JavaScript (ES6), 136 bytes

document.write("<pre>"+(

c=>s=>eval("for(r=Math.random,i=100,o=``;i--;o+=` `)for(j=r()*5;j-->0;)for(t=s[r(k=0)*s.length|0];l=t[k++];)o+=c[l][r()*c[l].length|0]")

)({ C: "st", V: "aeiou" })([ "CV", "CVC" ]))

Takes an object for the categories and an array for the syllable types.

JavaScript (ES6), 134 bytes
(c,s,r=s=>s[Math.random()*s.length|0],t="01234")=>[...Array(100)].map(_=>t.slice(r(t)).replace(/./g,_=>r(s)).replace(/./g,s=>r(c[s])))

Explanation:
(c,s,                               // Parameters
 r=s=>s[Math.random()*s.length|0],  // Select random character
 t="01234"                          // Number of syllables to skip
)=>[...Array(100)].map(_=>          // Generate 100 words
 t.slice(r(t))                      // Skip random number of syllables
  .replace(/./g,_=>r(s))            // Select syllables randomly
  .replace(/./g,s=>r(c[s])))        // Select letters randomly

Haskell, 95 bytes
import Test.QuickCheck
e=elements
c#s=mapM putStr=<<(generate$resize 5$listOf1$e s>>=mapM(e.c))

The categories are passed as a function from Char to String and the syllables types as a list of strings, e.g.
cat 'C' = "st"
cat 'V' = "aeiou"
syl = ["CV","CVC"]

Usage example: cat # syl -> tesat. Or with function/list literals: (\c->case c of 'C' -> "st"; 'V' -> "aeiou") # ["CV","CVC"]. Note: the function prints the generated word to stdout. If you try this within ghci, the return value is also printed, but that's a feature of the REPL and not of my code.
Dealing with random values in a purely functional language like Haskell is usually awkward. Luckily Test.QuickCheck provides some random generators and combinators for them that hide all the nastiness in a monad.
How it works:
input:
  s: list of syllable types
  c: categories as a function from Char to String

        e s             --  pick a random syllable type from s
           >>=mapM(e.c) --  for each letter: apply c and pick a random letter
                            from the returned string. We now have a random
                            generator for a single syllable
       listOf1          --  make a list of syllables of random length with
                            a minimum of 1
     resize 5           --  limit the maximum size to 5 (the list is not simply
                              cut if it is too long, all lengths are equally likely
   generate             --  run the generator. We now have a list of 1 to 5 syllables
mapM putStr=<<          --  print the syllables.

I'm happy that it works at all, maybe there's room for improvement.
Some more examples:
*Main> mapM_ (\_ -> do (cat#syl) ; putStrLn "" ) [1..10]
sisatassetto
se
ti
taso
sittos
tuttuste
tottu
satutustittes
sutetsetusut
tattatosote

Python 3.5, 227 223 210 206 201 bytes:
def k(u,*p):
 import itertools as i,random as r;y=[]
 for z in p:y+=[''.join(i)for i in i.product(*[u[i]for o in z for i in o])]
 for q in'1'*100:print(''.join([r.choice(y)for i in'1'*r.randint(1,5)]))

Takes the categories in as a Python dictionary (e.g {'C':'hello','K':'hoop'}) and the syllable types in as normal strings, with each separated by a comma (e.g. 'CK','CKC'). Output is in the form of 100 lines, with 1 word per line. Will add detailed explanation later.
Try it online! (repl.it)

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Map a list of indefinite size to a number!
It is well known, in the field of Mathematics studying infinity, that the Cartesian product of any finite amount of countable sets is also countable.
Your task is to write two programs to implement this, one to map from list to integer, one to map from integer to list.
Your function must be bijective and deterministic, meaning that 1 will always map to a certain list, and 2 will always map to another certain list, etc...
Earlier, we mapped integers to a list consisting only of 0 and 1.
However, now the list will consist of non-negative numbers.
Specs

Program/function, reasonable input/output format.
Whether the mapped integers start from 1 or starts from 0 is your choice, meaning that 0 doesn't have to (but may) map to anything.
The empty array [] must be encoded.
Input/output may be in any base.
Sharing code between the two functions is allowed.

Scoring
This is code-golf. Lowest score wins.
Score is the sum of lengths (in bytes) of the two programs/functions.

"However, now the list will consist of non-negative numbers."

So, to be clear, we're mapping N^inf -> N?

@Mego N^inf is not countable. N^k where k is any finite number is.

We have been discussing about this in chat.

Whether it starts from 1 or starts from 0 is your choice. Does that apply to the single integer and to the integers in the list.

Are two functions allowed, rather than two programs?

@Dennis Clarified.

@Mego Clarified.

If two functions are posted, may they interact with each other? I'm asking since some languages have a built-in function inverse.

@Dennis It is allowed.

Related: Pack sequences of non-negative integers

Related:A Mapping of Primes

Jelly, 18 16 bytes
List to integer, 10 8 bytes
TṪạL;³ÆẸ

Maps lists of non-negative integers to positive integers. Try it online!
Integer to list, 8 bytes
ÆE©Ḣ0ẋ®;

Maps positive integers to lists of non-negative integers . Try it online!
Background
Let p0, p1, p2, ⋯ be the sequence of prime numbers in ascending order.
For each list of non-negative integers A := [a1, ⋯, an], we map A to p0z(A)p1a1⋯pnan, where z(A) is the number of trailing zeroes of A.
Reversing the above map in straightforward. For a positive integer k, we factorize it uniquely as the product of consecutive prime powers n = p0α0p1α1⋯pnαn, where αn > 0, then reconstruct the list as [α1, ⋯, αn], appending α0 zeroes.
How it works
List to integer
TṪạL;³ÆẸ  Main link. Argument: A (list of non-negative integers)

T         Yield all indices of A that correspond to truthy (i.e., non-zero) items.
 Ṫ        Tail; select the last truthy index.
          This returns 0 if the list is empty.
   L      Yield the length of A.
  ạ       Compute the absolute difference of the last truthy index and the length.
          This yields the amount of trailing zeroes of A.
    ;³    Prepend the difference to A.
      ÆẸ  Convert the list from prime exponents to integer.

Integer to list
ÆE©Ḣ0ẋ®;  Main link. Input: k (positive integer)

ÆE        Convert k to the list of its prime exponents.
  ©       Save the list of prime exponents in the register.
   Ḣ      Head; pop the first exponent.
          If the list is empty, this yields 0.
    0ẋ    Construct a list of that many zeroes.
      ®;  Concatenate the popped list of exponents with the list of zeroes.

Example output
The first one hundred positive integers map to the following lists.
  1: []
  2: [0]
  3: [1]
  4: [0, 0]
  5: [0, 1]
  6: [1, 0]
  7: [0, 0, 1]
  8: [0, 0, 0]
  9: [2]
 10: [0, 1, 0]
 11: [0, 0, 0, 1]
 12: [1, 0, 0]
 13: [0, 0, 0, 0, 1]
 14: [0, 0, 1, 0]
 15: [1, 1]
 16: [0, 0, 0, 0]
 17: [0, 0, 0, 0, 0, 1]
 18: [2, 0]
 19: [0, 0, 0, 0, 0, 0, 1]
 20: [0, 1, 0, 0]
 21: [1, 0, 1]
 22: [0, 0, 0, 1, 0]
 23: [0, 0, 0, 0, 0, 0, 0, 1]
 24: [1, 0, 0, 0]
 25: [0, 2]
 26: [0, 0, 0, 0, 1, 0]
 27: [3]
 28: [0, 0, 1, 0, 0]
 29: [0, 0, 0, 0, 0, 0, 0, 0, 1]
 30: [1, 1, 0]
 31: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 32: [0, 0, 0, 0, 0]
 33: [1, 0, 0, 1]
 34: [0, 0, 0, 0, 0, 1, 0]
 35: [0, 1, 1]
 36: [2, 0, 0]
 37: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 38: [0, 0, 0, 0, 0, 0, 1, 0]
 39: [1, 0, 0, 0, 1]
 40: [0, 1, 0, 0, 0]
 41: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 42: [1, 0, 1, 0]
 43: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 44: [0, 0, 0, 1, 0, 0]
 45: [2, 1]
 46: [0, 0, 0, 0, 0, 0, 0, 1, 0]
 47: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 48: [1, 0, 0, 0, 0]
 49: [0, 0, 2]
 50: [0, 2, 0]
 51: [1, 0, 0, 0, 0, 1]
 52: [0, 0, 0, 0, 1, 0, 0]
 53: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 54: [3, 0]
 55: [0, 1, 0, 1]
 56: [0, 0, 1, 0, 0, 0]
 57: [1, 0, 0, 0, 0, 0, 1]
 58: [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 59: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 60: [1, 1, 0, 0]
 61: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 62: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 63: [2, 0, 1]
 64: [0, 0, 0, 0, 0, 0]
 65: [0, 1, 0, 0, 1]
 66: [1, 0, 0, 1, 0]
 67: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 68: [0, 0, 0, 0, 0, 1, 0, 0]
 69: [1, 0, 0, 0, 0, 0, 0, 1]
 70: [0, 1, 1, 0]
 71: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 72: [2, 0, 0, 0]
 73: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 74: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 75: [1, 2]
 76: [0, 0, 0, 0, 0, 0, 1, 0, 0]
 77: [0, 0, 1, 1]
 78: [1, 0, 0, 0, 1, 0]
 79: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 80: [0, 1, 0, 0, 0, 0]
 81: [4]
 82: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 83: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 84: [1, 0, 1, 0, 0]
 85: [0, 1, 0, 0, 0, 1]
 86: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 87: [1, 0, 0, 0, 0, 0, 0, 0, 1]
 88: [0, 0, 0, 1, 0, 0, 0]
 89: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 90: [2, 1, 0]
 91: [0, 0, 1, 0, 1]
 92: [0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
 93: [1, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 94: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 95: [0, 1, 0, 0, 0, 0, 1]
 96: [1, 0, 0, 0, 0, 0]
 97: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 98: [0, 0, 2, 0]
 99: [2, 0, 0, 1]
100: [0, 2, 0, 0]

This is brilliant.

Jelly, 13 12 bytes
Encode, 7 6 bytes
2Bṁx‘Ḅ

Try it online!
Decode, 6 bytes
ȯIBŒɠ’

Try it online!
Encodes positive integers in the run lengths of the binary representation. Since we may have zeros, we increment all numbers. For example, the list [0,1,4] is encoded as 10011111 in binary.
Numbers from 0 to 100 (Try it online!):
0                     []
1                     [0]
2                     [0, 0]
3                     [1]
4                     [0, 1]
5                     [0, 0, 0]
6                     [1, 0]
7                     [2]
8                     [0, 2]
9                     [0, 1, 0]
10                    [0, 0, 0, 0]
11                    [0, 0, 1]
12                    [1, 1]
13                    [1, 0, 0]
14                    [2, 0]
15                    [3]
16                    [0, 3]
17                    [0, 2, 0]
18                    [0, 1, 0, 0]
19                    [0, 1, 1]
20                    [0, 0, 0, 1]
21                    [0, 0, 0, 0, 0]
22                    [0, 0, 1, 0]
23                    [0, 0, 2]
24                    [1, 2]
25                    [1, 1, 0]
26                    [1, 0, 0, 0]
27                    [1, 0, 1]
28                    [2, 1]
29                    [2, 0, 0]
30                    [3, 0]
31                    [4]
32                    [0, 4]
33                    [0, 3, 0]
34                    [0, 2, 0, 0]
35                    [0, 2, 1]
36                    [0, 1, 0, 1]
37                    [0, 1, 0, 0, 0]
38                    [0, 1, 1, 0]
39                    [0, 1, 2]
40                    [0, 0, 0, 2]
41                    [0, 0, 0, 1, 0]
42                    [0, 0, 0, 0, 0, 0]
43                    [0, 0, 0, 0, 1]
44                    [0, 0, 1, 1]
45                    [0, 0, 1, 0, 0]
46                    [0, 0, 2, 0]
47                    [0, 0, 3]
48                    [1, 3]
49                    [1, 2, 0]
50                    [1, 1, 0, 0]
51                    [1, 1, 1]
52                    [1, 0, 0, 1]
53                    [1, 0, 0, 0, 0]
54                    [1, 0, 1, 0]
55                    [1, 0, 2]
56                    [2, 2]
57                    [2, 1, 0]
58                    [2, 0, 0, 0]
59                    [2, 0, 1]
60                    [3, 1]
61                    [3, 0, 0]
62                    [4, 0]
63                    [5]
64                    [0, 5]
65                    [0, 4, 0]
66                    [0, 3, 0, 0]
67                    [0, 3, 1]
68                    [0, 2, 0, 1]
69                    [0, 2, 0, 0, 0]
70                    [0, 2, 1, 0]
71                    [0, 2, 2]
72                    [0, 1, 0, 2]
73                    [0, 1, 0, 1, 0]
74                    [0, 1, 0, 0, 0, 0]
75                    [0, 1, 0, 0, 1]
76                    [0, 1, 1, 1]
77                    [0, 1, 1, 0, 0]
78                    [0, 1, 2, 0]
79                    [0, 1, 3]
80                    [0, 0, 0, 3]
81                    [0, 0, 0, 2, 0]
82                    [0, 0, 0, 1, 0, 0]
83                    [0, 0, 0, 1, 1]
84                    [0, 0, 0, 0, 0, 1]
85                    [0, 0, 0, 0, 0, 0, 0]
86                    [0, 0, 0, 0, 1, 0]
87                    [0, 0, 0, 0, 2]
88                    [0, 0, 1, 2]
89                    [0, 0, 1, 1, 0]
90                    [0, 0, 1, 0, 0, 0]
91                    [0, 0, 1, 0, 1]
92                    [0, 0, 2, 1]
93                    [0, 0, 2, 0, 0]
94                    [0, 0, 3, 0]
95                    [0, 0, 4]
96                    [1, 4]
97                    [1, 3, 0]
98                    [1, 2, 0, 0]
99                    [1, 2, 1]
100                   [1, 1, 0, 1]

Python 2, 88 bytes
d=lambda n:map(len,bin(n).split('1')[1:])
e=lambda l:int('1'.join(a*'0'for a in[2]+l),2)

Demo:
>>> for i in range(33):
...     print e(d(i)), d(i)
...
0 []
1 [0]
2 [1]
3 [0, 0]
4 [2]
5 [1, 0]
6 [0, 1]
7 [0, 0, 0]
8 [3]
9 [2, 0]
10 [1, 1]
11 [1, 0, 0]
12 [0, 2]
13 [0, 1, 0]
14 [0, 0, 1]
15 [0, 0, 0, 0]
16 [4]
17 [3, 0]
18 [2, 1]
19 [2, 0, 0]
20 [1, 2]
21 [1, 1, 0]
22 [1, 0, 1]
23 [1, 0, 0, 0]
24 [0, 3]
25 [0, 2, 0]
26 [0, 1, 1]
27 [0, 1, 0, 0]
28 [0, 0, 2]
29 [0, 0, 1, 0]
30 [0, 0, 0, 1]
31 [0, 0, 0, 0, 0]
32 [5]

Python 2, 130 bytes
Here’s a more “efficient” solution where the bit-length of the output is linear in the bit-length of the input rather than exponential.
def d(n):m=-(n^-n);return d(n/m/m)+[n/m%m+m-2]if n else[]
e=lambda l:int('0'+''.join(bin(2*a+5<<len(bin(a+2))-4)[3:]for a in l),2)

Uses the same algorithm as my solution :)

@KennyLau: I hadn’t looked at your solution. They look similar but not identical (0s and 1s are swapped). And yours fails to round-trip the empty list.

I see, thanks for reminding.

By the way, I said the output can be in any base.

Since sharing code between the functions is allowed, it looks like you can just build e to be the inverse for d: e=lambda l,i=0:l!=d(i)and-~e(l,i+1).

Python 2, 204 202 bytes
p=lambda x,y:(2*y+1<<x)-1
u=lambda n,x=0:-~n%2<1and u(-~n//2-1,x+1)or[x,n//2]
e=lambda l:l and-~reduce(p,l,len(l)-1)or 0
def d(n):
 if n<1:return[]
 r=[];n,l=u(n-1);exec"n,e=u(n);r=[e]+r;"*l;return[n]+r

Works by repeatedly applying a Z+ x Z+ <-> Z+ bijection, prepended by the list length.
0: []
1: [0]
2: [1]
3: [0, 0]
4: [2]
5: [0, 0, 0]
6: [1, 0]
7: [0, 0, 0, 0]
8: [3]
9: [0, 0, 0, 0, 0]
10: [1, 0, 0]
11: [0, 0, 0, 0, 0, 0]
12: [0, 1]
13: [0, 0, 0, 0, 0, 0, 0]
14: [1, 0, 0, 0]
15: [0, 0, 0, 0, 0, 0, 0, 0]
16: [4]
17: [0, 0, 0, 0, 0, 0, 0, 0, 0]
18: [1, 0, 0, 0, 0]
19: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
20: [0, 0, 1]
21: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
22: [1, 0, 0, 0, 0, 0]
23: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
24: [2, 0]
25: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
26: [1, 0, 0, 0, 0, 0, 0]
27: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
28: [0, 0, 0, 1]
29: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
30: [1, 0, 0, 0, 0, 0, 0, 0]
31: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

One question: which function is the "list to integer" function, and which is the "integer to list" function?

@zyabin101 e is list to integer, d is integer to list (encode/decode).

I like this solution.

Retina, 17 + 23 = 40 bytes
From list to integer:
\d+
$&$*0
^
1

1

Try it online!
From integer to list:
^1

S`1
m`^(0*)
$.1
¶
<space>

Try it online!
Uses Kaseorg's Algorithm.

16 bytes.

14 bytes.

JavaScript, 87 bytes
F=n=>n.toString(2).split(1).slice(1).map(_=>_.length)
G=a=>g=(i=0)=>F(i)+''==a?i:g(++i)

G goes through all inputs since it's shorter

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Find the positive divisors!
Definition
A number is positive if it is greater than zero.
A number (A) is the divisor of another number (B) if A can divide B with no remainder.
For example, 2 is a divisor of 6 because 2 can divide 6 with no remainder.
Goal
Your task is to write a program/function that takes a positive number and then find all of its divisors.
Restriction

You may not use any built-in related to prime or factorization.
The complexity of your algorithm must not exceed O(sqrt(n)).

Freedom

The output list may contain duplicates.
The output list does not need to be sorted.

Scoring
This is code-golf. Shortest solution in bytes wins.
Testcases
input    output
1        1
2        1,2
6        1,2,3,6
9        1,3,9

You probably mean divisor, not factor. And I guess you want to have a time complexity of O(sqrt(n)).

What is the difference between divisor and factor?

We talk about factors of e.g. a number, if the product of these results in the original number again, but the divisors are usually the numbers that divide said number without remainder.

@flawr Updated accordingly.

I suppose built-ins for divisors themselves are also disallowed. :P (Might want mention that explicitly.)

@MartinBüttner As long as their complexity does not exceed O(sqrt(n)).

Should have more examples. 99 (1 3 9 11 33 99)

PostgreSQL, 176 bytes
WITH c AS(SELECT * FROM(SELECT 6v)t,generate_series(1,sqrt(v)::int)s(r)WHERE v%r=0)
SELECT string_agg(r::text,',' ORDER BY r)
FROM(SELECT r FROM c UNION SELECT v/r FROM c)s

SqlFiddleDemo
Input:  (SELECT ...v)
How it works:

(SELECT ...v) - input
generate_series(1, sqrt(v)::int) - numbers from 1 to sqrt(n)
WHERE v%r=0 -filter divisors
wrap with common table expression to refer twice
SELECT r FROM c UNION SELECT v/r FROM c generete rest of divisors and combine
SELECT string_agg(r::text,',' ORDER BY r) produce final comma separated result

Input as table:
WITH c AS(SELECT * FROM i,generate_series(1,sqrt(v)::int)s(r)WHERE v%r=0)
SELECT v,string_agg(r::text,',' ORDER BY r)
FROM(SELECT v,r FROM c UNION SELECT v,v/r FROM c)s
GROUP BY v

SqlFiddleDemo
Output:
╔═════╦════════════════╗
║ v   ║   string_agg   ║
╠═════╬════════════════╣
║  1  ║ 1              ║
║  2  ║ 1,2            ║
║  6  ║ 1,2,3,6        ║
║  9  ║ 1,3,9          ║
║ 99  ║ 1,3,9,11,33,99 ║
╚═════╩════════════════╝

C#6, 75 bytes
string f(int r,int i=1)=>i*i>r?"":r%i==0?$"{i},{n(r,i+1)}{r/i},":n(r,i+1);

Based on the C# solution of downrep_nation, but recursive and golfed further down utilizing some new features from C#6.
Basic algorithm is the same as the one presented by downrep_nation. The for-loop is turned to a recursion, thus the second parameter. recursion start is done by the default parameter, thus the function is called with the required single starting-number alone.

using expression based functions without a block avoids the return statement
string interpolation within ternary operator allows to join string concatenation and conditions

As most answers here (yet) do not follow the exact output format from the examples, I keep it as it is, but as a drawback the function includes a single trailing comma at the result.

Nice first post!

R, 36 31 bytes
n=scan();c(d<-1:n^.5,n/d)^!n%%d

Try it online!
-5 bytes thanks to Robin Ryder

32 bytes with n^.5 instead of sqrt(n).

You can go down to 31 bytes by duplicating the 1 many times.

Matlab, 48 bytes
n=input('');a=1:n^.5;b=mod(n,a)<1;[a(b),n./a(b)]

How does this work?

Also, you devised an algorithm that I could not think of... How stupid I am.

I find all the divisos up to sqrt(n) and then put  each divisor d and n/d in my list.

Added some rules. Maybe could save you some bytes.

Indeed, I can omit unique now. Please note that changing the rules after people submitted answers it is usually frowned upon, consider using the Sandbox for future challenges!

I usually notify people if I change the rules to cause less harm.

What does ./ do?

./ is entry-wise division. (n is a scalar, a(b) is an matrix)

I haven't tested, but can't you use b=~mod(n,a) to save 1 byte?

J, 26 bytes
(],%)1+[:I.0=]|~1+i.@<.@%:

Explanation
(],%)1+[:I.0=]|~1+i.@<.@%:  Input: n
                        %:  Sqrt(n)
                     <.@    Floor(Sqrt(n))
                  i.@       Get the range from 0 to Floor(Sqrt(n)), exclusive
                1+          Add 1 to each
             ]              Get n
              |~            Get the modulo of each in the range by n
           0=               Which values are equal to 0 (divisible by n), 1 if true else 0
       [:I.                 Get the indices of ones
     1+                     Add one to each to get the divisors of n less than sqrt(n)
   %                        Divide n by each divisor
 ]                          Get the divisors
  ,                         Concatenate them and return

JavaScript (ES6) - 48 bytes
f=n=>[...Array(n+1).keys()].filter(x=>x&&!(n%x))

Not very efficient but works! Example below:

let f=n=>[...Array(n+1).keys()].filter(x=>x&&!(n%x));
document.querySelector("input").addEventListener("change", function() {
  document.querySelector("output").value = f(Number(this.value)).join(", ");
});
Divisors of <input type="number" min=0 step=1> are: <output></output>

Welcome to PPCG!

This is $\mathcal{O}(n)$ and as such is not valid.

05AB1E, 14 12 bytes
Code:
ÐtLDŠÖÏDŠ/ï«

Explanation:
Ð             # Triplicate input.
 tL           # Push the list [1, ..., sqrt(input)].
   D          # Duplicate that list.
    Š         # Pop a,b,c and push c,a,b.
     Ö        # Check for each if a % b == 0.
      Ï       # Only keep the truthy elements.
       D      # Duplicate the list.
        Š     # Pop a,b,c and push c,a,b
         /ï   # Integer divide
           «  # Concatenate to the initial array and implicitly print.

Uses CP-1252 encoding. Try it online!.

MATL, 12 bytes
tX^:\~ftGw/h

The approach is similar to that in @flawr's answer.
Try it online!
Explanation
t      % take input N. Duplicate.
X^:    % Generate range from 1 to sqrt(N)
\      % modulo (remainder of division)
~f     % indices of zero values: array of divisors up to sqrt(N)
tGw/   % element-wise divide input by those divisors, to produce rest of divisors
h      % concatenate both arrays horizontally

I do often wonder whether the combinded code of programs written in MATL would make a good RNG.

@flawr That probably applies to pretty every code golf language :-)

Python 2, 64 bytes
lambda n:sum([[x,n/x]for x in range(1,int(n**.5+1))if n%x<1],[])

This anonymous function outputs a list of divisors. The divisors are computed by trial division of integers in the range [1, ceil(sqrt(n))], which is O(sqrt(n)). If n % x == 0 (equivalent to n%x<1), then both x and n/x are divisors of n.
Try it online

Jelly, 9 bytes
½Rḍ³Tµ³:;

As the other answers, this is O(√n) if we make the (false) assumption that integer division is O(1).
How it works
½Rḍ³Tµ³:;  Main link. Argument: n

½          Compute the square root of n.
 R         Construct the range from 1 to the square root.
  ḍ³       Test each integer of that range for divisibility by n.
    T      Get the indices of truthy elements.
     µ     Begin a new, monadic chain. Argument: A (list of divisors)
      ³:   Divide n by each divisor.
        ;  Concatenate the quotients with A.

Try it online!

Let us continue this discussion in chat.

Javascript, 47 bytes

d=(n,f=1,s='')=>n==f?s+n:d(n,f+1,n%f?s:s+f+',')

Mathematica, 50 bytes
Similar to @flawr's solution.
Performs trail division for x from 1 up to the square root of n and if divisible, saves it to a list as x and n / x.
(#2/#)~Join~#&@@{Cases[Range@Sqrt@#,x_/;x∣#],#}&

Note that ∣ requires 3 bytes to represent in UTF-8, making the 48 character string require 50 bytes in UTF-8 representation.

Usage
  f = (#2/#)~Join~#&@@{Cases[Range@Sqrt@#,x_/;x∣#],#}&
  f[1]
{1, 1}
  f[2]
{2, 1}
  f[6]
{6, 3, 1, 2}
  f[9]
{9, 3, 1, 3}

Well, it requires 3 bytes...

@KennyLau Yes, I was wrong, should have double-checked

JavaScript (ES6), 66 62 bytes
f=(n,d=1)=>d*d>n?[]:d*d-n?n%d?f(n,d+1):[d,...f(n,d+1),n/d]:[d]

I thought I'd write a version that returned a sorted deduplicated list, and it actually turned out to be 4 bytes shorter...

C#, 87 bytes

Golfed
String m(int v){var o="1";int i=1;while(++i<=v/2)if(v%i==0)o+=","+i;o+=","+v;return o;}

Ungolfed
String m( Int32 v ) {
    String o = "1";
    Int32 i = 1;

    while (++i <= v / 2)
        if (v % i == 0)
            o += "," + i;

    o += "," + v;

    return o;
}

Full code
using System;
using System.Collections.Generic;

namespace N {
    class P {
        static void Main( string[] args ) {
            List<Int32> li = new List<Int32>() {
                1, 2, 6, 9,
            };

            foreach (Int32 i in li) {
                Console.WriteLine( i + " »> " + m( i ) );
            }

            Console.ReadLine();
        }

        static String m( Int32 v ) {
            String o = "1";
            Int32 i = 1;

            while (++i <= v / 2)
                if (v % i == 0)
                    o += "," + i;

            o += "," + v;

            return o;
        }
    }
}

Releases

v1.0 - 87 bytes - Initial solution.

Notes

In the Golfed code, I use var's and int's instead of String's and Int32's to make the code shorter, while in the Ungolfed Code and Full Code I use String's and Int32's to make the code more readable.

I've heard that for is generally better than while.

Your solution has a complexity of O(n) instead of O(sqrt(n))...

@KennyLau it depends of the situation, in this case having a for loop would have the same length that the while loop has. In this case it is irrelevant having on or the having the other.

But in this case it can save you a byte...

Lua, 83 bytes
s=''x=io.read()for i=1,x do if x%i==0 then s=s..i..', 'end end print(s:sub(1,#s-2))

I couldn't do better, unfortunately

welcome to PPCG, hope you'll enjoy this site! 2. you can change ==0 to <1 to save some bytes. 3. you can use the ternary structure instead of if then end, but i don't know if it wil save any bytes. 4. your algorithm's complexity is O(n) which does not meet the requirement.

All right. Does the list need to be ordered, or formatted appropriately?

"
The output list may contain duplicates.
The output list does not need to be sorted.
"

Right lol. And do I need to print the result or an array containing it is enough?

Well, either you print it or you return it (inside a function).

Perl 6, 40 bytes
{|(my@a=grep $_%%*,^.sqrt+1),|($_ X/@a)}

Explanation:
{
  # this block has an implicit parameter named $_

  # slip this list into outer list:
  |(

    my @a = grep
                 # Whatever lambda:
                 # checks if the block's parameter ($_)
                 # is divisible by (%%) this lambda's parameter (*)

                 $_ %% *,

                 # upto and exclude the sqrt of the argument
                 # then shift the Range up by one
                 ^.sqrt+1
                 # (0 ..^ $_.sqrt) + 1

                 # would be clearer if written as:
                 # 1 .. $_.sqrt+1
  ),
  # slip this list into outer list
  |(

    # take the argument and divide it by each value in @a
    $_ X/ @a

    # should use X[div] instead of X[/] so that it would return
    # Ints instead of Rats
  )
}

Usage:
my &divisors = {|(my@a=grep $_%%*,^.sqrt+1),|($_ X/@a)}

.say for (1,2,6,9,10,50,99)».&divisors

(1 1)
(1 2 2 1)
(1 2 3 6 3 2)
(1 3 9 3)
(1 2 10 5)
(1 2 5 50 25 10)
(1 3 9 99 33 11)

IA-32 machine code, 27 bytes
Hexdump:
60 33 db 8b f9 33 c0 92 43 50 f7 f3 85 d2 75 04
ab 93 ab 93 3b c3 5a 77 ec 61 c3

Source code (MS Visual Studio syntax):
    pushad;
    xor ebx, ebx;
    mov edi, ecx;
myloop:
    xor eax, eax;
    xchg eax, edx;
    inc ebx;
    push eax;
    div ebx;
    test edx, edx;
    jnz skip_output;
    stosd;
    xchg eax, ebx;
    stosd;
    xchg eax, ebx;
skip_output:
    cmp eax, ebx;
    pop edx;
    ja myloop;
    popad;
    ret;

First parameter (ecx) is a pointer to output, second parameter (edx) is the number. It doesn't mark the end of output in any way; one should prefill the output array with zeros to find the end of the list.
A full C++ program that uses this code:
#include <cstdint>
#include <vector>
#include <iostream>
#include <sstream>
__declspec(naked) void _fastcall doit(uint32_t* d, uint32_t n) {
    _asm {
        pushad;
        xor ebx, ebx;
        mov edi, ecx;
    myloop:
        xor eax, eax;
        xchg eax, edx;
        inc ebx;
        push eax;
        div ebx;
        test edx, edx;
        jnz skip_output;
        stosd;
        xchg eax, ebx;
        stosd;
        xchg eax, ebx;
    skip_output:
        cmp eax, ebx;
        pop edx;
        ja myloop;
        popad;
        ret;
    }
}
int main(int argc, char* argv[]) {
    uint32_t n;
    std::stringstream(argv[1]) >> n;
    std::vector<uint32_t> list(2 * sqrt(n) + 3); // c++ initializes with zeros
    doit(list.data(), n);
    for (auto i = list.begin(); *i; ++i)
        std::cout << *i << '\n';
}

The output has some glitches, even though it follows the spec (no need for sorting; no need for uniqueness).

Input: 69
Output:
69
1
23
3

The divisors are in pairs.

Input: 100
Output:
100
1
50
2
25
4
20
5
10
10

For perfect squares, the last divisor is output twice (it's a pair with itself).

Input: 30
Output:
30
1
15
2
10
3
6
5
5
6

If the input is close to a perfect square, the last pair is output twice. It's because of the order of checks in the loop: first, it checks for "remainder = 0" and outputs, and only then it checks for "quotient < divisor" to exit the loop.

c#, 87 bytes
void f(int r){for(int i=1;i<=Math.Sqrt(r);i++){if(r%i==0)Console.WriteLine(i+" "+r/i);}

i do not know if this works for all numbers, i suspect it does.
but the complexity is right, so thats already something isnt it

Ruby, 56 bytes
->n{a=[];(1..Math.sqrt(n)).map{|e|a<<e<<n/e if n%e<1};a}

SmileBASIC, 49 bytes
INPUT N
FOR D=1TO N/D
IF N MOD D<1THEN?D,N/D
NEXT

Uses the fact that D>N/D = D>sqrt(N) for positive numbers

C, 87 81 bytes
Improved by @ceilingcat, 81 bytes:
i,j;main(n,b)int**b;{for(;j=sqrt(n=atoi(b[1]))/++i;n%i||printf("%u,%u,",i,n/i));}

Try it online!

My original answer, 87 bytes:
i;main(int n,char**b){n=atoi(b[1]);for(;(int)sqrt(n)/++i;n%i?:printf("%u,%u,",i,n/i));}

Compile with gcc div.c -o div -lm, and run with ./div <n>.

Bonus: An even shorter variant with O(n) time complexity and hardcoded n (46 bytes + length of n):
i,n=/*INSERT VALUE HERE*/;main(){for(;n/++i;n%i?:printf("%u,",i));}

Edit: Thank you to @Sriotchilism O'Zaic for pointing out that inputs should not be hardcoded, I modified the main submission to take the input via argv.

Is n the input?  Putting the input in a variable is not an accepted way of doing input here for a number of reasons.  You can see more about our accepted and non-accepted input and output forms here: https://codegolf.meta.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods.  And if you are curious about a specific language (e.g. C) you can look here: https://codegolf.meta.stackexchange.com/questions/11924/new-users-guides-to-golfing-rules-in-specific-languages.

@SriotchilismO'Zaic Yes, n is the input. I'll try modifying it so it takes the input some other way. Thank you for the info!

APL(NARS), 22 chars, 44 bytes
{v∪⍵÷v←k/⍨0=⍵∣⍨k←⍳⌊√⍵}

test:
  f←{v∪⍵÷v←k/⍨0=⍵∣⍨k←⍳⌊√⍵}
  f 1
1
  f 2
1 2
  f 6
1 2 6 3
  f 9
1 3 9
  f 90
1 2 3 5 6 9 90 45 30 18 15 10

C# (Visual C# Interactive Compiler), 40 bytes
Just providing an updated C# answer
n=>Enumerable.Range(1,n).Where(x=>n%x<1)

Try it online!


text:
Find the n-th perfect power!
A perfect power is a number of the form \$a^b\$, where \$a>0\$ and \$b>1\$.
For example, \$125\$ is a perfect power because it can be expressed as \$5^3\$.
Goal
Your task is to write  a program/function that finds the \$n\$-th perfect power, given a positive integer \$n\$.
Specs

The first perfect power is \$1\$ (which is \$1^2\$).
Input/output in any reasonable format.
Built-ins are allowed.

Further information

OEIS A001597

Scoring
This is code-golf. Shortest solution in bytes wins.
Testcases
input  output
1      1
2      4
3      8
4      9
5      16
6      25
7      27
8      32
9      36
10     49

Uptil what number should this work? Infinity?

A reasonable amount.

What about a language that uses only a data type of one bit?

@ghosts_in_the_code I think a language like that is considered in the loopholes.

not loophole but rule-escapist

@Agawa001 Yes it is a standard loophole which are no longer funny.

Related. Related. Related.

Mathematica, 34 bytes
(Union@@Array[#^#2#&,{#,#}])[[#]]&

Generates an \$n\times n\$ array \$A_{ij} = i^{1+j}\$, flattens it, and returns the \$n\$th element.

Jelly, 11 bytes
µÆE;¬g/’µ#Ṫ

Try it online!.
Background
Every positive integer \$k\$ can be factorized uniquely as the product of powers of the first \$m\$ primes, i.e., \$k=p_1^{\alpha_1}\cdots p_m^{\alpha_m}\$, where \$\alpha_m>0\$.
We have that \$a^b\$ (\$b>1\$) for some positive integer \$a\$ if and only if \$b\$ is a divisor of all exponents \$\alpha_j\$.
Thus, an integer \$k > 1\$ is a perfect power if and only if \$\gcd(α_1, ⋯, α_m) ≠ 1\$.
How it works
µÆE;¬g/’µ#Ṫ  Main link. No arguments.

µ            Make the chain monadic, setting the left argument to 0.
        µ#   Find the first n integers k, greater or equal to 0, for which the
             preceding chain returns a truthy value.
             In the absence of CLAs, n is read implicitly from STDIN.
 ÆE          Compute the exponents of the prime factorization of k.
   ;¬        Append the logical NOT of k, i.e., 0 if k > 0 and 1 otherwise.
             This maps 1 -> [0] and [0] -> [1].
     g/      Reduce the list of exponents by GCD.
             In particular, we achieved that 1 -> 0 and 0 -> 1.
       ’     Decrement; subtract 1 from the GCD.
             This maps 1 to 0 (falsy) and all other integers to a truthy value.
          Ṫ  Tail; extract the last k.

I haven't seen STDIN at all. I have no idea how to use it at all.

Nice use of the definition of perfect power having to do with prime factorization. Could you include this algorithm in the description?

@KennyLau Done.

I don't understand how 21^2 includes the first or third prime in its factorization. Could you please help me understand what you mean by "Every positive integer k can be factorized uniquely as the product of powers of the first m primes...where [the exponent] a_n > 0?" It seems to me in the factorization for 21^2 the exponents for p = 2 and p = 5 are zero.

@גלעדברקן Sorry, that should have been a_m > 0. The previous m-1 exponents may include zeroes.

......cool, tx!

05AB1E, 12 bytes
Code:
LD>m€`{Ú`¹<@

Uses CP-1252 encoding. Try it online!.

Octave, 57 31 30 bytes
@(n)unique((1:n)'.^(2:n+1))(n)

I just noticed again that Octave does not need ndgrid (while Matlab does)=)

CJam, 16 bytes
ri_),_2f+ff#:|$=

Test it here.
Explanation
This uses a similar idea to LegionMammal's Mathematica answer.
ri    e# Read input and convert to integer N.
_),   e# Duplicate, increment and turn into range [0 1 ... N].
_2f+  e# Duplicate and add two to each element to get [2 3 ... N+2].
ff#   e# Compute the outer product between both lists over exponentiation.
      e# This gives a bunch of perfect powers a^b for a ≥ 0, b > 1.
:|    e# Fold set union over the list, getting all unique powers generated this way.
$     e# Sort them.
=     e# Retrieve the N+1'th power (because input is 1-based, but CJam's array access
      e# is 0-based, which is why we included 0 in the list of perfect powers.

Jelly, 9 bytes
*þḊFQṢị@o

Try it online!
As far as I can tell, only the þ quick didn't exist when the challenge was posted, but this 10 byter would've worked back then as well as now.
How it works
*þḊFQṢị@o - Main link. Takes n on the left
  Ḋ       - Yield [2, 3, ..., n]
 þ        - Create an n×(n-1) matrix then
            for each entry (i,j) (i = 1,2,...,n and j = 2,3,...n),
            fill it with the following:
*         -   i*j
   F      - Flatten the matrix
    Q     - Remove duplicates
     Ṣ    - Sort
            For all n > 1, this yields an ordered list of perfect powers below n*n
            For n = 1, this yields an empty list
      ị@  - Take the nth item in this list. n = 1 yields 0
        o - Replace 0 with n, to handle n = 1

Sage (version 6.4, probably also others): 64 63
lambda n:[k for k in range(1+n^2)if(0+k).is_perfect_power()][n]

Creates a lambda function that returns nth perfect power. We rely on the fact that it is found within the first n^2 integers. (The 1+n^2 is necessary for n=1,2. The 0+k bit is necessary to convert int(k) to Integer(k).)
Byte off for xrange->range, thanks Dennis.
Just a fun fact: 0 is a perfect power by Sage's standards, fortunately, because then 1 is the 1st element of the list, not 0th :)

So this is Python except for the prime power part?

@CatsAreFluffy And is_perfect_power()

Pyth - 12 11 bytes
Obvious approach, just goes through and checks all numbers.
e.ffsI@ZTr2

Test Suite.

J, 29 bytes
Based on the @LegionMammal978's method.
<:{[:/:~@~.[:,/[:(^/>:)~>:@i.

Usage
   f =: <:{[:/:~@~.[:,/[:(^/>:)~>:@i.
   f " 0 (1 2 3 4 5 6 7 8 9 10)
1 4 8 9 16 25 27 32 36 49

Explanation
<:{[:/:~@~.[:,/[:(^/>:)~>:@i.
                           i.  Create range from 0 to n-1
                        >:     Increments each in that range, now is 1 to n
               [:              Cap, Ignores input n
                    >:         New range, increment from previous range to be 2 to n+1 now
                  ^/           Forms table using exponentation between 1..n and 2..n+1
             ,/                Flattens table to a list
         ~.                    Takes only distinct items
     /:~                       Sorts the list
<:                             Decrements the input n (since list is zero-based index)
  {                            Selects value from resulting list at index n-1

MATL, 9 bytes
:tQ!^uSG)

Try it online
This is a port of Flawr's Octave solution to MATL, make the matrix of powers up to n^(n+1), and get the n-th one.

Julia, 64 32 bytes
n->sort(∪([1:n]'.^[2:n+1]))[n]

This is an anonymous function that accepts an integer and returns an integer. To call it, assign it to a variable.
The idea here is the same as in LegionMammal's Mathematica answer: We take the outer product of the integers 1 to n with 2 to n + 1, collapse the resulting matrix column-wise, take unique elements, sort, and get the nth element.
Try it online! (includes all test cases)

><>, 108 bytes
:1)?v  >n;
$:@@\&31+2>2$:@@:@
:1=?\@$:@*@@1-
:~$~<.1b+1v!?(}:{:~~v?(}:{:v?=}:{
1-:&1=?v~~>~61.     >~1+b1.>&

This program requires the input number to be present on the stack before running.
It took quite a lot to reduce the number of wasted bytes down to 7!
After a check to see if the input is 1, the program checks each number, n, from 4 in turn to see if it's a perfect power. It does this by starting with a=b=2. If a^b == n, we've found a perfect power, so decrement the number of perfect powers left to find - if we've already found the right number, output.
If a^b < n, b is incremented. If a^b > n, a is incremented. Then, if a == n, we've found that n isn't a perfect power, so increment n, resetting a and b.

JavaScript (ES6), 87
n=>(b=>{for(l=[i=0,1];b<n*n;++b)for(v=b;v<n*n;)l[v*=b]=v;l.some(x=>n==i++?v=x:0)})(2)|v

Less golfed
f=n=>{
  for(b=2, l=[0,1]; b < n*n; ++b)
    for(v = b; v < n*n;)
      l[v*=b] = v;
  i = 0;
  l.some(x => n == i++ ? v=x : 0);
  return v;
  // shorter alternative, but too much memory used even for small inputs
  // return l.filter(x=>x) [n-1];
}

Test

f=n=>(b=>{for(l=[i=0,1];b<n*n;++b)for(v=b;v<n*n;)l[v*=b]=v;l.some(x=>n==i++?v=x:0)})(2)|v

function test(){
  var v=+I.value
  O.textContent=f(v)
}

test()
<input type=number id=I value=10><button onclick='test()'>-></button>

Actually, 18 bytes
;;u@ⁿr;`;√≈²=`M@░E

Try it online! (may not work due to needing an update)
Explanation:
;;u@ⁿr;`;√≈²=`M@░E
;;u@ⁿr              push range(n**(n+1))
      ;`;√≈²=`M@░   filter: take if
        ;√≈²=         int(sqrt(x))**2 == x
                 E  get nth element

Husk, 10 bytes
!¹OuṠ×^tḣ→

Try it online!
Explanation
!¹OuṠ×^tḣ→ Range 1..n+1 (ḣ called with 1 given an empty list)
    Ṡ      hookf: Ṡ f g x = f (g x) x
     ×^     f: apply power to all possible pairs from two lists
       t    g: tail (1..n → 2..n)
   u       all unique powers
  O        sort in ascending order
!¹         element at index n

Husk, 10 bytes
!¹uO§×^…2ḣ

Try it online!
Dominic Van Essen's solution.
Explanation
!¹uO§×^…2ḣ
    §      fork: § f g h x = f (g x) (h x)
     ×^     f: apply power to all possible pairs from two lists
       …2   g: inclusive range from 2..n (works for n<2)
         ḣ  h: range from 1..n
   O        sort in ascending order
  u         all unique powers
!¹         element at index n

I got !¹uO§×^…2ḣ which is also 10 bytes.  You'll get the upvote when you post your explanation...

@DominicvanEssen haha.. nice.

@DominicvanEssen added yours as well.

R, 44 bytes
n=scan();unique(sort(outer(1:n,2:n,`^`)))[n]

Try it online!
Same approach as the Mathematica answer.

JavaScript (ES7), 104 bytes
n=>(a=[...Array(n)]).map(_=>a.every(_=>(p=i**++j)>n*n?0:r[p]=p,i+=j=1),r=[i=1])&&r.sort((a,b)=>a-b)[n-1]

Works by computing all powers not greater than n², sorting the resulting list and taking the nth element.

Java, 126
r->{int n,i,k;if(r==1)return r;for(n=i=2,r--;;){for(k=i*i;k<=n;k*=i)if(k==n){i=--r>0?++n:n;if(r<1)return n;}if(--i<2)i=++n;}}

Would it be shorter to use recursion?

Good, idea, needs a lot of planning though.

Python 3, 82 bytes
f=lambda n,i=0:n and f(n-any(a**b==i for a in range(i)for b in range(i)),i+1)or~-i

Try it online!

05AB1E, 9 bytes
µNDÓ2šθ2@

Try it online or verify a few more test cases.
Explanation:
µ         # Loop until the counter_variable (0 by default) equals the (implicit) input:
 ND       #  Push the current 0-based loop-index `N` twice
   Ó      #  Pop one, and push all its exponents of prime factorization [a,b,c,d,...] in
          #  [2^a,3^b,5^c,7^d,...]
          #  (for N=0 and N=1, this will results in an empty list)
    2š    #  Prepend a 2 (for the edge cases N=0 and N=1)
      θ   #  Pop the list, and leave just the last value
       2@ #  Check if this is larger than or equal to 2
          #  (if it is: implicitly increase the counter_variable by 1)
          # (after the loop, implicitly output the last `N` that's still on the stack)

Minor note: the @ in my answer using the latest 05AB1E version is a builtin for >=, whereas the @ used in @Adnan's existing 05AB1E answer using the legacy 05AB1E version is a builtin to push the \$n^{th}\$ item on the stack.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Bijective mapping from integers to a variable number of trits
This challenge is a harder version of this one.
A variable number of trits is an array of 0 or more trits (a trit is a ternary digit). So [0, 2, 2, 1] is a variable number of trits, but so is [].
Write a function or program that, given an non-negative integer returns a variable number of trits such that every integer has a one-to-one (bijective) mapping with an array.
There are an infinite amount of such mappings, you are free to construct one as you please, but it must be one-to-one. Your mapping must conceptually be one-to-one for an arbitrarily sized integer, but it's OK if your implementation fails for large integers due to numerical limits of types in your preferred language (e.g. C's int).
As an example of what is not a one-to-one mapping, is simply listing the ternary digits of the integer. In such a system 5 becomes [1, 2] (because 1*3^1 + 2*3^0 = 5), but it's not one-to-one, because [0, 1, 2] also means 5 (because 0*3^2 + 1*3^1 + 2*3^0 = 5).
It should be fairly obvious that a mapping is not one-to-one if it skips an integer (e.g. it doesn't work for 5), but I'd like to make it clear that skipping a variable trit array is also not one-to-one. You must map to every possible variable trit array, including [].
Bonus challenge
You will be awarded the official Super Smaht® Award™ if your answer includes an algorithm (not necessarily in your golfed program) that not only works for base 2 or 3, but for all bases.

Shortest code in bytes wins.

input/output format?

@KennyLau The standard stuff, you can write a program or function, taking a list  of trits, or a string containing the trits (e.g. [1, 0, 2] or "102" or "1, 0, 2") and you must output a single integer to stdout, function return, etc.

Pyth, 6 bytes
tjyhQ3

Explanation:
    Q    Input number.
   h     Add 1.
  y      Multiply by 2.
 j   3   Convert to base 3 as a list.
t        Remove the first element.

Test suite
Inverse function: Pyth, 14 bytes
t/i+-2%sQ2Q3 2

Explanation:
        Q        Input list.
       s         Sum.
      %  2       Modulo 2.
    -2           Subtract from 2.
   +      Q      Prepend to input list.
  i        3     Convert from base 3.
 /           2   Divide by 2.
t                Subtract 1.

Test suite
The bijection looks like this:
0: []
1: [1]
2: [0]
3: [2]
4: [0, 1]
5: [1, 0]
6: [1, 2]
7: [2, 1]
8: [0, 0]
9: [0, 2]
10: [1, 1]
11: [2, 0]
12: [2, 2]
13: [0, 0, 1]
14: [0, 1, 0]
15: [0, 1, 2]
16: [0, 2, 1]
17: [1, 0, 0]
18: [1, 0, 2]
19: [1, 1, 1]
⋮

General base
To make this work in any base b, simply replace 3 with b, 2 with (b − 1), and y with *(b − 1).

No way... how come the algorithm is so simple...

Also, it would be interesting if you show the inverse function.

@orlp Added the inverse function!

I think I can prove that this algorithm generalizes to all bases.

JavaScript, 24 bytes
f=n=>n?f(--n/3|0)+n%3:''

Try it online!
Implements the standard ternary bijective numeration, except with the digits reduced by 1.
How it works: First, check if n is 0, returning the empty string if so. Otherwise, n is pre-decremented, and that value is divided by 3 and rounded down (|0 is a short way to do the rounding) and passed recursively to f – the final digit will contribute 1, 2, or 3, while the rest contribute a multiple of 3, so \$\lfloor\frac{n-1}{3}\rfloor\$ is the value the non-final digits should represent on their own. Finally, n%3 appends the final digit, reduced by 1 from the standard (n having already been decremented).

Jelly, 3 bytes
ḃ3’

Try it online!
ḃ3   Convert to bijective base 3
  ’  Decrement all digits

Inverse, 3 bytes
‘ḅ3

Try it online!
‘    Increment all digits
 ḅ3  Convert from base 3

Both versions can be made to use an arbitrary base by removing the 3.

Jelly, 12 bytes
ḤR‘b3Ḣ’$Ðḟị@

There is no empty list in Jelly; it is represented as 0 (an integer not a list).
For other bases: change Ḥ to ×n and b3 to bn, where n is the intended base.
Try it online!
Test suite.
For other bases
It only costs 11 bytes if given base as second input.
Try it online!
Test suite.
Algorithm
I thought of appending a 1 before the list and then convert it to a ternary.
That way, [0,0] will become 100 = 9 while [0,0,0] will become 1000 = 27.
However, a problem arises: that 2011 and 1011 both map to [0,1,1].
I only need numbers whose ternary representation starts with 1.
Therefore, I generated those whose ternary representation starts with 1, and then use their index instead.
That is, the list begins as [1, 3, 4, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...].
Therefore:

1 will be mapped to 1
2 will be mapped to 3
3 will be mapped to 4
4 will be mapped to 5
5 will be mapped to 9
n will be mapped to a(n) where a is that list.

There's another problem: both 0 and 1 are mapped to the empty list. Therefore, I removed 1 from the list, making a = [3, 4, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...].
Those are the integers whose ternary representation starts with 1, except 1.
The same algorithm can be applied to other bases.

Jelly, 6 bytes
‘Ḥb3ṫ2

Translation of Kaseorg's answer in Pyth.
Try it online!
Hardcoded base: try it online!
Given base: try it online!

CJam, 9 bytes
ri)_+3b(;

Translation of Kaseorg's answer in Pyth.
Try it online!

JavaScript (ES6), 31 bytes
n=>(n*2+2).toString(3).slice(1)

Since everyone else is translating @AndreasKaseorg's fine answer. Generic version (36 bytes):
b=>n=>(-~n*~-b).toString(b).slice(1)


text:
Find the number of ways to choose `n` objects from `r` objects with repetition so that every object has a matching neighbour
For example, if n is 5 and r is 2, it would mean the number of lists below:
[1,1,1,1,1]
[1,1,1,2,2]
[1,1,2,2,2]
[2,2,1,1,1]
[2,2,2,1,1]
[2,2,2,2,2]

which is 6.
If n is 4 and r is 3:
[1,1,1,1]
[1,1,2,2]
[1,1,3,3]
[2,2,1,1]
...
[3,3,3,3]

which is 9.
where each item has a neighbour whose value is the same.
For example, [1,2,1,1,2] is not counted, because both 2 are alone.
Goal
Your task is to write a program/function which takes two inputs in any order, and which produces the required output.
Detail
You can assume that r≥2.
Scoring
This is code-golf. Shortest solution in bytes wins.
Bonus
Multiply your score by 0.3 if the complexity of your program is below O(e^n).
For example, 10 bytes becomes 3 bytes.
Testcases
Can be generated from this Pyth test suite.
Usage: two lines per testcase, n on top, r below.
n r output
2 5 5
4 4 16
6 3 33
8 2 26

Additional information
When r=2: OEIS A006355.

what about ranking complexities from O(n^k) to O(n), craming all approaches below O(r^n) in one jar isnt that judicious (in addition that i dont claim this knowingly of any solution-shortcut)

@Jakube Yes you can.

I don't understand those test cases. In particular, if n=2, then there can only be r solutions i.e. two of the same object.

@Neil Yes, you are correct.

@Jakube Thanks, fixed.

Also, you're using the O notation wrong - being O(e^n) means being not asymptotically greater than e^n - so n is O(e^n), and being "less than O(e^n)" doesn't make much sense.

@proudhaskeller Colloquially, "less than O(something)" means "has an upper bound of less than something". As the meaning is understood, extra qualifications are unnecessary.

Pyth, 14 bytes * 0.3 = 4.2 bytes
*Quh*~+ZGtQtE0

Try it online: Demonstration. Input r on the first line and n on the second line.
Complexity is O(n).
Explanation:
Let f(n, r) be the number of ways to create such a list with the last number being 0. Obviously it doesn't matter if we take 0 or any other number.
It's easy to see, that the following recursion holds:
f(n, r) = 0                                  ... if n < 2
f(n, r) = sum(f(i, r), i <= n-2) * (r-1) + 1 ... otherwise

If n == 0, than the list cannot end with the number 0. If n == 1, than the only number in the list has no neighbor. Therefore both cases have the value zero.
If n >= 2, than it could end in 2, 3, ... n zeros. The digit before the last zero can be any of the number 1, 2, ..., r-1. These are r-1 possibilities. Therefore I'll add up all f(i,n) and multiply by r-1. At the end I'll have to add 1 (for the case that all digits are zeros).
The result to the question than is: r * f(n, r), since the list can end in any of the r numbers.
In my code I make use of the predefined variable Z = 0. It will contain the last computed sum so far.
*Quh*~+ZGtQtE0   implicit: Q = first input number (r)
  u        tE0   start with G=0, do the following input-1 (n-1) times:
     ~+ZG           add G to Z
   h*~ Z tQ         and update G to the value Z*(Q-1) + 1
                    (using the old value of Z)
*Q               multiply the result with Q

Explanation please? :)

Very nice indeed!

@jakube  how much a detailed explanation costs ? (joking but i m very excited for the algorithm behind this)

JavaScript (ES6), 64 (70 * 0.3 = 21) bytes
(n,r)=>[...Array(n)].map((m,i,a)=>a[i+2]=(s=s+m|0)*~-r+r).slice(-2)[0]

Now runs in linear time!

How does it not qualify for the bonus?

@KennyLau The number of calls required is the nth Fibonacci number.

I see. Not memoized...

Well, you could just translate the Pyth algorithm?

Haskell, 16.5 (55 bytes)
r#n=l!!(n-1)where l=0:r:r:w l;w(x:y:s)=r*(x+y)-x:w(y:s)

It uses this recursive definition:
f(n,r) = r*f(n-2,r) + (r-1)*f(n-3,r)

and uses O(n) time.
Usage: evaluate r#n

Isn't the above solution O(e^n)?

@KennyLau Pretty much like the javascript answer, this is less than 2^n, and phi^n calls, and phi<2<e

According to Wikipedia, every thing of the form O(k^n) where k>1 counts as O(e^n)...

Its not about the exact value of base, but the form of the time complexity. So for practical purposes, this is exponential.

@KennyLau that may be the notation some people use for "exponential", I do not know, but if you would actually look up the definition of big O notation, you would see that if 0<x<y then O(x^n) is asymptotically smaller than O(y^n), so O(2^n) applies for the bonus. If you would like the bonus to apply when the program uses less than exponential time, please write so in the challenge.

@Optimizer oh, I see. the e is very confusing.

Jelly, 8 bytes
ṗŒɠ€’Ạ€S

Try it online!
How it works
ṗŒɠ€’Ạ€S - Main link. Takes r on the left and n on the right
ṗ        - n'th Cartesian power of [1,2,3,...,n]
   €     - Over each:
 Œɠ      -   Lengths of adjacent elements
    ’    - Decrement, mapping 1 to 0 and everything else to a positive integer
      €  - Over each:
     Ạ   -   All non-zero?
       S - Sum, counting the 1s

Husk, 6 bytes
#oΛtgπ

Try it online!
Explanation
#oΛtgπ
     π cartesian power n of range 1..r
#o     number of lists which satisfy
    g   adjacent elements grouped
  Λ     all the groups
   t    are non empty when popped from


text:
Counting triangles with integer perimeter
Mary has given John two sticks of lengths a and b respectively, where a and b are positive integers.
John is very curious.
He would like to know how many triangles with integer perimeter can be formed, by having one additional side.
Please help him find it out.
(This is my first time composing this kind of stupid stories in coding problems, so forgive me if it is too stupid.)
Specs

Given two integers a and b, find the number of triangles with integer perimeter that can be formed, by having one additional side.

Details

Congruent triangles are congruent.
Flat triangles are flat out uncounted.
Zero-sided triangles are counted zero times.

Scoring
This is code-golf. Shortest solution in bytes wins.
Testcases
a b output
1 2 1
3 3 5
9 7 13

I like your wording.

Also, is a full program needed or just a function? It makes a big difference in java. Even in javascript.

@Bálint There are default rules for this.

For a=1 and b=2, why can't I have two triangles, 1,1,2 and 1,2,2?

@Neil 1,1,2 is flat.

So it is. Never mind me.

Jelly, 3 bytes
«Ḥ’

Try it online!
Explanation
«   min(a,b)
 Ḥ          *2
  ’           -1

(Not quite rigorous) proof of correctness:

Let x = min(a,b) and y = max(a,b), and let z be a potential third side.
We can't have z ≤ y-x, because for z < y-x the triangle can't be closed and for z = y-x it would be degenerate. See triangle inequality.
We can't have z ≥ y+x, for the same reasons.
Every integer z in between is valid and gives a different triangle. That means we've got (y+x) - (y-x) - 1 = 2x - 1 different triangles.

Could you please prove your algorithm?

Let's say we have a and b, and a>b. The minimum length triangle is a-b+1, the maximum length is a+b-1. The amount of triangles is maximum-minimum+1=a+b-1-(a-b+1)+1=2b-2+1=2b-1

Could you at least cite the triangle inequality? :)

@KennyLau If you insist...

CJam, 7 bytes
l~e<2*(

Test it here.
Explanation
l~  e# Read and evaluate input.
e<  e# min(a,b).
2*  e# Double.
(   e# Decrement.

For a proof of correctness, see my Jelly answer which uses the same algorithm.

05AB1E, 3 bytes
Using @MartinBüttner's algorithm. Code:
·<ß

Explanation:
·    # Double the input.
 <   # Decrement by 1.
  ß  # Take the smallest value.

Uses CP-1252 encoding. Try it online!.

Labyrinth, 20 bytes
Thanks to Sp3000 for some help while golfing this.
<""-}:?:?
"`
{
++(!@

Try it online!
Explanation
It turns out that the 2*min(a,b)-1 approach isn't the shortest in Labyrinth. Instead it's easier to compute (a+b)-|a-b|-1.
Labyrinth primer:

Labyrinth has two stacks of arbitrary-precision integers, main and aux(iliary), which are initially filled with an (implicit) infinite amount of zeros. I will usually represent these like Main [... a b | c d ...] Aux, where Main grows to the right, Aux grows to the left and ... represents the implicit zeros at the bottom.
The source code resembles a maze, where the instruction pointer (IP) follows corridors when it can (even around corners). The code starts at the first valid character in reading order, i.e. in the top left corner in this case. When the IP comes to any form of junction (i.e. several adjacent cells in addition to the one it came from), it will pick a direction based on the top of the main stack. The basic rules are: turn left when negative, keep going ahead when zero, turn right when positive. And when one of these is not possible because there's a wall, then the IP will take the opposite direction. The IP also turns around when hitting dead ends.
The source code can be modified at runtime using <>^v which cyclically shift a row or column of the grid.

The code starts on the < which immediately modifies the source code. This is a common golfing trick in Labyrinth whenever a program starts with a long-ish bit of linear code. Afterwards, the source looks like this, with the IP still on the <:
""-}:?:?<
"`
{
++(!@

Since the IP is now in a dead end, it has to start moving left. The linear code does the following:
Op      Explanation                    Stacks
?       Read integer a from STDIN.     Main [... a | ...] Aux
:       Duplicate.                     Main [... a a | ...] Aux
?       Read integer b from STDIN.     Main [... a a b | ...] Aux
:       Duplicate.                     Main [... a a b b | ...] Aux
}       Move b over to aux.            Main [... a a b | b ...] Aux
-       Subtract b from a on main.     Main [... a (a-b) | b ...] Aux

The code now enters the only nonlinear part of the code which compues -abs(x), (where I'm now using < and v to indicate entry and exit points):
""<
"`
v

The " is a no-op (i.e. it does nothing), whereas the ` multiplies the top of the main stack by -1. Let's go through the three possible cases of control flow:

If a == b, i.e. a-b is zero, the IP keeps moving west on the first ". Then it hits a corner on the the second " and has to turn south. Again, it keeps moving south on the third " and leaves this 2x2 block. All in all, nothing happens to zeros at all.
If a > b, i.e. a-b is positive, the IP turns south on the first ". The ` then switches the top of the main stack to b-a and the IP has to take a turn west. On the next " the top of the stack is now negative, and the IP turns south. Therefore, if the top of the stack is positive, its sign will be negated by this block.
If a < b, i.e. a-b is negative, then the IP also turns towards the ` , which now makes it positive. That means the IP turns north on the next no-op. It hits the corner and turns east, and turns south once more so that it reaches the ` a second time. At this point, the control flow is no different from a positive input, so after applying ` twice, we're back at a-b which is negative and leaves the loop. Despite doing a lot more stuff, negative inputs are also unaffected by this part of the code.

Now that we've computed -abs(a-b), the remainder of the code is all linear again:
Op      Explanation                    Stacks
                                       [... a -|a-b| | b ...]
{       Move b back to main.           [... a -|a-b| b | ...]
+       Add.                           [... a (-|a-b|+b) | ...]
+       Add.                           [... (a+b-|a-b|) | ...]
(       Decrement.                     [... (a+b-|a-b|-1) | ...]
!       Print as integer.              [... | ...]
@       Terminate program.

Cubix, 18 19 bytes
Not overly short, but a tad more interesting to do due to a lack of a minimum function.Saved a byte with a big thanks to Martin Büttner
-@IOIU>wu+..U;?;2*

This wraps onto a cube with edge length 2 and ends up looking like this
    - @
    I O
I U > w u + . .
U ; ? ; 2 * . .
    . .
    . .

Explanation that hopefully can be followed. Try it here
Getting parameters from STDIN
    -                # This section gets input, u-turns onto top face,
    I                # heading up, gets another input and performs a subtraction.
I U                  # Carries on around the bottom of the cube upto the next part.

Determine least and leaving it at TOS
    > w              # Hits the ? going up.  if TOS is negative turn left, pop stack
U ; ? ;              # and U-turn onto bottom face heading back up to ?.
    .                # If 0 redirect through > and w to ; popping stack, heading right.
    .                # If positive redirect right to ; which pops TOS

Output the answer and end
      @              # Push 2 onto the stack, multiply, U-turn onto input which
      O              # gives us -1 for the stack, add it then u-turn to the left
I       u +          # onto the top face, output the TOS as number and end
U       2 *

-@IOIU>wu+..U;?;2* saves a byte.

@MartinBüttner Thank you very much.  Beautiful use of the input to get the -1.  I would never have thought of that.

Javascript full program 88 42 bytes
a=prompt();b=prompt();alert((a<b?a:b)*2-1)

I hate prompts, even java is better in that aspect.
Javascript function 73 31 21 bytes
(a,b)=>(a<b?a:b)*2-1

Testable version:

c=(a,b)=>(a<b?a:b)*2-1

var d = prompt("enter first number");
var e = prompt("enter second number");
alert(c(d, e));

Thanks to @Neil for saving 8 bytes.
Thanks goes to @MartinBüttner for the algorithm and for saving 1 byte.

I'll add an answer in java then. (Java is my first language actually...)

What's the space doing in max=a- -b-1;?

Why not use a lambda? You can always use functions instead of full programs unless explicitly forbidden.

@DenkerAffe I always work on full programs before going on to lamdas, I did that one too.

@KennyLau If I don't put it there, it throws a syntax error, as -- is the decrement operator. doing a- -b casts both of them to numbers, then subtracts the negative of b from a, thus it's doing the same as adding it.

You don't need the {return} in your lambda; if you just have an expression then it's returned by default.

You don't need to assign the lambda to a variable.

Retina, 14 bytes
M!`(1+) \1
 1

Input and output in unary.
Try it online! (Modified to run multiple decimal test cases at once.)
Explanation
Still the same approach as my CJam and Jelly answers (the latter contains a proof of correctness), but this time using string processing of unary representations.
M!`(1+) \1

This finds min(a,b) by matching the first string of 1s that can be found in both of them. This being a match stage and using the ! the result is actually min(a,b) min(a,b) since the entire match is written back.
 1

This simply matches the separating a space and a single 1 and removes them. This leaves a string of 2*min(a,b) - 1 characters, which is the desired result.

k (8 bytes)
Using the Jelly/CJam algorithm
-1+2*min

e.g.
k)-1+2*(&). 10 10
19

Java 55 42 bytes
int c(int a,int b){return (a<b?a:b)*2-1);}

Java has lambdas; use them to save bytes! :)

APL, 6 bytes
1-⍨2×⌊

This is a dyadic function train that accepts integers on the right and left and returns an integer. It uses the 2 min(a, b) - 1 approach.
Try it here (includes all test cases)

Actually, 3 bytes
mτD

Try it online or verify all test cases at once
This uses the same 2*min(a,b)-1 approach that basically every other solutions uses. Each operation (minimum, double, decrement) is its own single-byte command.

J, 7 bytes
1-~2*<.

This is a tacit verb.
1-~2*<.
1-~      reflexive minus (i.e. R - 1)
   2*    double
     <.  lesser of

Jolf, 4 bytes
m±♀j

Replace ♀ with a literal \x12 byte, or try it here!
Explanation
m±♀j
  ♀j  min of j and implicit input
m±    2*(^)-1

PHP 36 bytes
function($a,$b){echo min($a,$b)*2-1}

Thanks goes to @MartinBüttner for the algorithm

C# 6.0 - 34 bytes
int a(int b,int c)=>(b<c?b:c)*2-1;

Wow, C# has lambdas?! :o

Unbalanced parentheses...

@KennyLau Thanks for telling. It's fixed now :). And yes, C# does have lambdas. C# 6.0 allows named functions to have an lambda expressions their bodies. This saved me from using the 'return' keyword and brackets.