Generate all possible integers

Question

Input: you are given 2 integers, n and k. n is a positive (>= 1) integer, and k an integer, which is the number of times you are allowed to use n.

Output: output all of the non-negative integers that can be formed using at most k n's using these mathematical operations: +, -, *, /, and parentheses.

Edit: if your language supports removing elements from an array/set/etc., the requirement of non-negative integers is required. If not, then it is not required.

The only numerical value that can exist in the expression is n (however many times). If the value of the expression exceeds the maximum value of whatever data storage you have (such as int or long, etc.), you have to compensate for it (there is no maximum value that can be given for n).

Speed is not important, but shortest code wins!

Bonuses:

• -50: include exponentiation in the list of mathematical operations. Exponentiation is defined to be that the base is some expression of n, not e = 2.71828...

• -50: include the floor (or ceiling) functions if a given possible operation is not an integer.

Examples

> 2 2
0 1 4
> 4 3
3 4 5 12 20 64 ...

(Sample inputs/outputs do not necessarily include bonuses)

Answer 1

Javascript (E6) 215 (315 - 2*50 bonus) 252

Edit Simplified. Correct bug of 0 missing

Defined as a function, then counting 10 more byte for output using alert()

Important Really this one is not valid according to the rules, because javascript can not handle big numbers. For instance with parameters 2,5 it can't find 2^2^2^2^2 (ie 2^65536). A number this big is 'Infinity' in javascript.

Golfed

F=(n,k,g={})=>{k+=k-1;for (l=i=1;x=i.toString(6),l+=!!x[l],l<k;i++)if(x.split(0).length*2==l+1){for(s=[n,n],p=l;o=x[--p];)
if(-o)b=s.pop(),a=s.pop(),s.push(o<2?a+b:o<3?a-b:o<4?a*b:o<5?a/b:Math.pow(a,b));else s.push(x[p]=n);
r=Math.floor(s.pop());r>=0&isFinite(r)&!isNaN(r)&!g[r]&&(g[r]=x)}return Object.keys(g)};

To be golfed. I have an idea I want to share: use a postfix notation. In postfix any type of expression is made just of values and operators - no parentheses needed. The postfix notation can be translated to usual algebraic infix notation - but that's out of scope in this challenge.

Usage

alert(F(4,3))

Output 1,2,3,4,5,8,12,16,20,32,64,252,256,260,1024,4096,65536,4294967296,1.3407807929942597e+154

Ungolfed

F=(n, k, g={})=>{
  k += k - 1;
  // Count in base 6 - '0' means Value, '1'..'5' means operators
  // A valid expression starts with Value twice, then n operators intermixed with n-1 Values
  // x: Coded expression, l: Expression length, k Expression limit length from param
  for (l = i = 1; x = i.toString(6), l += !!x[l], l<k; i++)
    if (x.split(0).length*2 == l+1) // check balancing values/operators
    {
      for (s = [n,n], p = l; o = x[--p];) // Calc stack starts with N,N
        if (-o) // If not '0'
          b=s.pop(),a=s.pop(), // Do calc
          s.push(o<2 ? a+b : o<3 ? a-b : o<4 ? a*b : o<5 ? a/b : Math.pow(a,b))
        else // Push value 
          s.push(n) // 
      r = Math.floor(s.pop()); // Last result in stack
      r >= 0 & isFinite(r) & !isNaN(r) & !g[r] && (g[r]=x) // Put in hashtable avoiding duplicates
    }
  // Uncomment this to see the postfix expression list 
  // for (i in g) console.log(i, [n,n,...[...g[i]].reverse().map(v=>v>0?'x+-*/^'[v]:n)])
  return Object.keys(g) // Retust list of hashtable keys
}

First version this is more complicated but maybe easier to follow

Display the postfix expression for each number

F=(n,k)=> {
  var i,l,s;
  var cmd;
  var op='n+-*/^'
  var bag = {}
  function Calc(val,pos,stack)
  {
    while (c = cmd[pos])
    {
        if (c == 0)
        {
            stack.push(n);
            cmd[pos] = n
            pos++
        }
        else 
        {
            var b=stack.pop(), a=stack.pop();
            stack.push(c < 2 ? a+b : c < 3 ? a-b : c < 4 ? a*b : c < 5 ? a/b
               : Math.pow(a,b))
            cmd[pos]=op[c]
            pos++
        }
    }
    var res = Math.floor(stack.pop())
    if (res > 0 && isFinite(res) && !isNaN(res) && !bag[res]) 
    {
       bag[res] = cmd
    }
  }
  k=k+k-3;
  for (i=1;s=i.toString(6), !s[k]; i++)
  {
       l=s.split(0).length;
       if (l+l-1==s.length) 
       {
          var cmd = (s+'00').split('').reverse()
          Calc(n, 0, [], cmd.map(c=>op[c]).join(' '))
       }
  }

  for (i in  bag)
  {
    console.log(bag[i],'=', i)
  }
}

Usage

F(4,3)

Output

[4, 4, "/"] = 1
[4, 4, "+", 4, "/"] = 2
[4, 4, 4, "/", "-"] = 3
[4, 4, "-", 4, "+"] = 4
[4, 4, "/", 4, "+"] = 5
[4, 4, "+"] = 8
[4, 4, "+", 4, "+"] = 12
[4, 4, "*"] = 16
[4, 4, "*", 4, "+"] = 20
[4, 4, "+", 4, "*"] = 32
[4, 4, "*", 4, "*"] = 64
[4, 4, "^", 4, "-"] = 252
[4, 4, "^"] = 256
[4, 4, "^", 4, "+"] = 260
[4, 4, "^", 4, "*"] = 1024
[4, 4, "+", 4, "^"] = 4096
[4, 4, "*", 4, "^"] = 65536
[4, 4, "^", 4, "^"] = 4294967296
[4, 4, 4, "^", "^"] = 1.3407807929942597e+154

Answer 2

Python 2, 249 characters - 50 bonus = 199

from operator import*
n,k=input()
def g(a):
 if len(a)==1:yield a[0]
 else:
  for i in range(1,len(a)):
   for l in g(a[:i]):
    for r in g(a[i:]):
     for o in[add,sub,mul,pow]:
      yield o(l,r)
     if r:yield l/r
print set(map(abs,g([n]*k)))

Sample runs:

2,2
set([0, 1, 4])
4,3
set([32, 65536, 2, 3, 4, 5, 0, 1, 64, 252, 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096L, 12, 1024, 4096, 20, 4294967296L, -252, -12, -4, -3, 260])

This claims the exponentiation bonus of -50 points. Allowing exponentiation can give some staggeringly large results for small inputs (remove pow from the list of operators to try without exponentiation).

Answer 3

Mathematica, 105 bytes - 100 bonus = 5

Note: This does not currently support parentheses. Fixing once the OP clarifies the challenge.

If negative integers are okay, too, this scores 1 instead.

f[n_,k_]:=Union@Abs@Floor@ToExpression[ToString@n&~Array~k~Riffle~#<>""&/@Tuples[Characters@"*+/-^",k-1]]

Somewhat ungolfed:

f[n_, k_] :=
 Union@Abs@Floor@
    ToExpression[
     ToString@n &~Array~k~Riffle~# <> "" & /@
      Tuples[Characters@"*+/-^", k - 1]
     ]

I'm claiming both bonuses for including exponentiation and flooring non-integer results.

Examples:

f[2, 2]
f[4, 3]

Out[1] = {0, 1, 4}
Out[2] = {0, 3, 4, 5, 12, 20, 64, 252, 260, 1024, 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096}

Answer 4

Python 2.x: 32 (132-(50+50))

from itertools import*
l=list("+-*/")+["**"]
f=lambda n,k:{abs(eval(j)) for j in(`k`+`k`.join(i)+`k`for i in product(l,repeat=n-1))}

I'll claim both bonuses: x/y behaves like you would expect floor(x/y) to behave, and it does support powers.

Demo:

from itertools import*
l=list("+-*/")+["**"]
f=lambda n,k:{abs(eval(j)) for j in(`k`+`k`.join(i)+`k`for i in product(l,repeat=n-2))}


f(2,2)
Out[2]: {0, 1, 2, 3, 6, 8, 16}

f(2,3)
Out[3]: {0, 2, 3, 4, 6, 9, 12, 24, 27, 30, 81, 7625597484987L}

f(3,2)
Out[4]: {0, 1, 2, 3, 4, 5, 6, 8, 10, 14, 16, 18, 32, 65536}

f(4,2)
Out[5]: 
{0,
 1,
 2,
 3,
 4,
 5,
 6,
 7,
 8,
 9,
 10,
 12,
 14,
 15,
 16,
 17,
 18,
 20,
 30,
 32,
 34,
 64,
 32768,
 65534,
 65538,
 131072,
 2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880933348101038234342907263181822949382118812668869506364761547029165041871916351587966347219442930927982084309104855990570159318959639524863372367203002916969592156108764948889254090805911457037675208500206671563702366126359747144807111774815880914135742720967190151836282560618091458852699826141425030123391108273603843767876449043205960379124490905707560314035076162562476031863793126484703743782954975613770981604614413308692118102485959152380195331030292162800160568670105651646750568038741529463842244845292537361442533614373729088303794601274724958414864915930647252015155693922628180691650796381064132275307267143998158508811292628901134237782705567421080070065283963322155077831214288551675554073345107213112427399562982719769150054883905223804357045848197956393157853510018992000024141963706813559840464039472194016069517690156119726982337890017641517190051133466306898140219383481435426387306539552969691388024158161859561100640362119796101859534802787167200122604642492385111393400464351623867567078745259464670903886547743483217897012764455529409092021959585751622973333576159552394885297579954028471943529913543763705986928913757153740001986394332464890052543106629669165243419174691389632476560289415199775477703138064781342309596190960654591300890188887588084733625956065444888501447335706058817090162108499714529568344061979690565469813631162053579369791403236328496233046421066136200220175787851857409162050489711781820400187282939943446186224328009837323764931814789848119452713007440220765680910376203999203492023906626264491909167985461515778839060397720759279378852241294301017458086862263369284725851403039615558564330385450688652213114813638408384778263790459607186876728509763471271988890680478243230394718650525660978150729861141430305816927924971409161059417185352275887504477592218301158780701975535722241400019548102005661773589781499532325208589753463547007786690406429016763808161740550405117670093673202804549339027992491867306539931640720492238474815280619166900933805732120816350707634351669869625020969023162859350071874190579161241536897514808261904847946571736601005892476655445840838334790544144817684255327207315586349347605137419779525190365032198020108764738368682531025183377533908861426184800374008082238104076468878471647552945326947661700424461063311238021134588694532200116564076327023074292426051582811070387018345324567635625951430032037432740780879056283663406965030844225855967039271869461158513793386475699748568670079823960604393478850861649260304945061743412365828352144806726676841807083754862211408236579802961200027441324438432402331257403545019352428776430880232850855886089962774458164680857875115807014743763867976955049991643998284357290415378143438847303484261903388841494031366139854257635577105335580206622185577060082551288893332226436281984838613239570676191409638533832374343758830859233722284644287996245605476932428998432652677378373173288063210753211238680604674708428051166488709084770291208161104912555598322366244868556651402684641209694982590565519216188104341226838996283071654868525536914850299539675503954938371853405900096187489473992880432496373165753803673586710175783994818471798498246948060532081996066183434012476096639519778021441199752546704080608499344178256285092726523709898651539462193004607364507926212975917698293892367015170992091531567814439791248475706237804600009918293321306880570046591458387208088016887445835557926258465124763087148566313528934166117490617526671492672176128330845273936469244582892571388877839056300482483799839692029222215486145902373478222682521639957440801727144146179559226175083889020074169926238300282286249284182671243405751424188569994272331606998712986882771820617214453142574944015066139463169197629181506579745526236191224848063890033669074365989226349564114665503062965960199720636202603521917776740668777463549375318899587866282125469797102065747232721372918144666659421872003474508942830911535189271114287108376159222380276605327823351661555149369375778466670145717971901227117812780450240026384758788339396817962950690798817121690686929538248529830023476068454114178139110648560236549754227497231007615131870024053910510913817843721791422528587432098524957878034683703337818421444017138688124249984418618129271198533315382567321870421530631197748535214670955334626336610864667332292409879849256691109516143618601548909740241913509623043612196128165950518666022030715613684732364660868905014263913906515063908199378852318365059897299125404479443425166774299659811849233151555272883274028352688442408752811283289980625912673699546247341543333500147231430612750390307397135252069338173843322950701049061867539433130784798015655130384758155685236218010419650255596181934986315913233036096461905990236112681196023441843363334594927631946101716652913823717182394299216272538461776065694542297877071383198817036964588689811863210976900355735884624464835706291453052757101278872027965364479724025405448132748391794128826423835171949197209797145936887537198729130831738033911016128547415377377715951728084111627597186384924222802373441925469991983672192131287035585307966942713416391033882754318613643490100943197409047331014476299861725424423355612237435715825933382804986243892498222780715951762757847109475119033482241412025182688713728193104253478196128440176479531505057110722974314569915223451643121848657575786528197564843508958384722923534559464521215831657751471298708225909292655638836651120681943836904116252668710044560243704200663709001941185557160472044643696932850060046928140507119069261393993902735534545567470314903886022024639948260501762431969305640666366626090207048887438898907498152865444381862917382901051820869936382661868303915273264581286782806601337500096593364625146091723180312930347877421234679118454791311109897794648216922505629399956793483801699157439700537542134485874586856047286751065423341893839099110586465595113646061055156838541217459801807133163612573079611168343863767667307354583494789788316330129240800836356825939157113130978030516441716682518346573675934198084958947940983292500086389778563494693212473426103062713745077286156922596628573857905533240641849018451328284632709269753830867308409142247659474439973348130810986399417379789657010687026734161967196591599588537834822988270125605842365589539690306474965584147981310997157542043256395776070485100881578291408250777738559790129129407309462785944505859412273194812753225152324801503466519048228961406646890305102510916237770448486230229488966711380555607956620732449373374027836767300203011615227008921843515652121379215748206859356920790214502277133099987729459596952817044582181956080965811702798062669891205061560742325686842271306295009864421853470810407128917646906550836129916694778023822502789667843489199409657361704586786242554006942516693979292624714524945408858422726153755260071904336329196375777502176005195800693847635789586878489536872122898557806826518192703632099480155874455575175312736471421295536494084385586615208012115079075068553344489258693283859653013272046970694571546959353658571788894862333292465202735853188533370948455403336565356988172582528918056635488363743793348411845580168331827676834646291995605513470039147876808640322629616641560667508153710646723108461964247537490553744805318226002710216400980584497526023035640038083472053149941172965736785066421400842696497103241919182121213206939769143923368374709228267738708132236680086924703491586840991153098315412063566123187504305467536983230827966457417620806593177265685841681837966106144963432544111706941700222657817358351259821080769101961052229263879745049019254311900620561906577452416191913187533984049343976823310298465893318373015809592522829206820862230332585280119266496314441316442773003237792274712330696417149945532261035475145631290668854345426869788447742981777493710117614651624183616680254815296335308490849943006763654806102940094693750609845588558043970485914449584445079978497045583550685408745163316464118083123079704389849190506587586425810738422420591191941674182490452700288263983057950057341711487031187142834184499153456702915280104485145176055306971441761368582384102787659324662689978418319620312262421177391477208004883578333569204533935953254564897028558589735505751235129536540502842081022785248776603574246366673148680279486052445782673626230852978265057114624846595914210278122788941448163994973881884622768244851622051817076722169863265701654316919742651230041757329904473537672536845792754365412826553581858046840069367718605020070547247548400805530424951854495267247261347318174742180078574693465447136036975884118029408039616746946288540679172138601225419503819704538417268006398820656328792839582708510919958839448297775647152026132871089526163417707151642899487953564854553553148754978134009964854498635824847690590033116961303766127923464323129706628411307427046202032013368350385425360313636763575212604707425311209233402837482949453104727418969287275572027615272268283376741393425652653283068469997597097750005560889932685025049212884068274139881631540456490350775871680074055685724021758685439053228133770707415830756269628316955687424060527726485853050611356384851965918968649596335568216975437621430778665934730450164822432964891270709898076676625671517269062058815549666382573829274182082278960684488222983394816670984039024283514306813767253460126007269262969468672750794346190439996618979611928750519442356402644303271737341591281496056168353988188569484045342311424613559925272330064881627466723523751234311893442118885085079358163848994487544756331689213869675574302737953785262542329024881047181939037220666894702204258836895840939998453560948869946833852579675161882159410981624918741813364726965123980677561947912557957446471427868624053750576104204267149366084980238274680575982591331006919941904651906531171908926077949119217946407355129633864523035673345588033313197080365457184791550432654899559705862888286866606618021882248602144999973122164138170653480175510438406624412822803616648904257377640956326482825258407669045608439490325290526337532316509087681336614242398309530806549661879381949120033919489494065132398816642080088395554942237096734840072642705701165089075196155370186264797456381187856175457113400473810762763014953309735174180655479112660938034311378532532883533352024934365979129341284854970946826329075830193072665337782559314331110963848053940859283988907796210479847919686876539987477095912788727475874439806779824968278272200926449944559380414608770641941810440758269805688038949654616587983904660587645341810289907194293021774519976104495043196841503455514044820928933378657363052830619990077748726922998608279053171691876578860908941817057993404890218441559791092676862796597583952483926734883634745651687016166240642424241228961118010615682342539392180052483454723779219911228595914191877491793823340010078128326506710281781396029120914720100947878752551263372884222353869490067927664511634758101193875319657242121476038284774774571704578610417385747911301908583877890152334343013005282797038580359815182929600305682612091950943737325454171056383887047528950563961029843641360935641632589408137981511693338619797339821670761004607980096016024823096943043806956620123213650140549586250615282588033022908385812478469315720323233601899469437647726721879376826431828382603564520699468630216048874528424363593558622333506235945002890558581611275341783750455936126130852640828051213873177490200249552738734585956405160830583053770732533971552620444705429573538361113677523169972740292941674204423248113875075631319078272188864053374694213842169928862940479635305150560788126366206497231257579019598873041195626227343728900516561111094111745277965482790471250581999077498063821559376885546498822938985408291325129076478386322494781016753491693489288104203015610283386143827378160946341335383578340765314321417150655877547820252454780657301342277470616744241968952613164274104695474621483756288299771804186785084546965619150908695874251184435837306590951460980451247409411373899927822492983367796011015387096129749705566301637307202750734759922943792393824427421186158236161317886392553095117188421298508307238259729144142251579403883011359083331651858234967221259621812507058113759495525022747274674369887131926670769299199084467161228738858457584622726573330753735572823951616964175198675012681745429323738294143824814377139861906716657572945807804820559511881687188075212971832636442155336787751274766940790117057509819575084563565217389544179875074523854455200133572033332379895074393905312918212255259833790909463630202185353848854825062897715616963860712382771725621313460549401770413581731931763370136332252819127547191443450920711848838366818174263342949611870091503049165339464763717766439120798347494627397822171502090670190302469762151278521956142070806461631373236517853976292092025500288962012970141379640038055734949269073535145961208674796547733692958773628635660143767964038430796864138563447801328261284589184898528048048844180821639423974014362903481665458114454366460032490618763039502356402044530748210241366895196644221339200757479128683805175150634662569391937740283512075666260829890491877287833852178522792045771846965855278790447562192663992008409302075673925363735628390829817577902153202106409617373283598494066652141198183810884515459772895164572131897797907491941013148368544639616904607030107596818933741217575988165127000761262789169510406315857637534787420070222051070891257612361658026806815858499852631465878086616800733264676830206391697203064894405628195406190685242003053463156621891327309069687353181641094514288036605995220248248886711554429104721929134248346438705368508648749099178812670565665387191049721820042371492740164460943459845392536706132210616533085662021188968234005752675486101476993688738209584552211571923479686888160853631615862880150395949418529489227074410828207169303387818084936204018255222271010985653444817207470756019245915599431072949578197878590578940052540122867517142511184356437184053563024181225473266093302710397968091064939272722683035410467632591355279683837705019855234621222858410557119921731717969804339317707750755627056047831779844447637560254637033369247114220815519973691371975163241302748712199863404548248524570118553342675264715978310731245663429805221455494156252724028915333354349341217862037007260315279870771872491234494477147909520734761385425485311552773301030342476835865496093722324007154518129732692081058424090557725645803681462234493189708138897143299831347617799679712453782310703739151473878692119187566700319321281896803322696594459286210607438827416919465162267632540665070881071030394178860564893769816734159025925194611823642945652669372203155504700213598846292758012527715422016629954863130324912311029627923723899766416803497141226527931907636326136814145516376656559839788489381733082668779901962886932296597379951931621187215455287394170243669885593888793316744533363119541518404088283815193421234122820030950313341050704760159987985472529190665222479319715440331794836837373220821885773341623856441380700541913530245943913502554531886454796252260251762928374330465102361057583514550739443339610216229675461415781127197001738611494279501411253280621254775810512972088465263158094806633687670147310733540717710876615935856814098212967730759197382973441445256688770855324570888958320993823432102718224114763732791357568615421252849657903335093152776925505845644010552192644505312073756287744998163646332835816140330175813967359427327690448920361880386754955751806890058532927201493923500525845146706982628548257883267398735220457228239290207144822219885587102896991935873074277815159757620764023951243860202032596596250212578349957710085626386118233813318509014686577064010676278617583772772895892746039403930337271873850536912957126715066896688493880885142943609962012966759079225082275313812849851526902931700263136328942095797577959327635531162066753488651317323872438748063513314512644889967589828812925480076425186586490241111127301357197181381602583178506932244007998656635371544088454866393181708395735780799059730839094881804060935959190907473960904410150516321749681412100765719177483767355751000733616922386537429079457803200042337452807566153042929014495780629634138383551783599764708851349004856973697965238695845994595592090709058956891451141412684505462117945026611750166928260250950770778211950432617383223562437601776799362796099368975191394965033358507155418436456852616674243688920371037495328425927131610537834980740739158633817967658425258036737206469351248652238481341663808061505704829059890696451936440018597120425723007316410009916987524260377362177763430621616744884930810929901009517974541564251204822086714586849255132444266777127863728211331536224301091824391243380214046242223349153559516890816288487989988273630445372432174280215755777967021666317047969728172483392841015642274507271779269399929740308072770395013581545142494049026536105825409373114653104943382484379718606937214444600826798002471229489405761853892203425608302697052876621377373594394224114707074072902725461307358541745691419446487624357682397065703184168467540733466346293673983620004041400714054277632480132742202685393698869787607009590048684650626771363070979821006557285101306601010780633743344773073478653881742681230743766066643312775356466578603715192922768440458273283243808212841218776132042460464900801054731426749260826922155637405486241717031027919996942645620955619816454547662045022411449404749349832206807191352767986747813458203859570413466177937228534940031631599544093684089572533438702986717829770373332806801764639502090023941931499115009105276821119510999063166150311585582835582607179410052528583611369961303442790173811787412061288182062023263849861515656451230047792967563618345768105043341769543067538041113928553792529241347339481050532025708728186307291158911335942014761872664291564036371927602306283840650425441742335464549987055318726887926424102147363698625463747159744354943443899730051742525110877357886390946812096673428152585919924857640488055071329814299359911463239919113959926752576359007446572810191805841807342227734721397723218231771716916400108826112549093361186780575722391018186168549108500885272274374212086524852372456248697662245384819298671129452945515497030585919307198497105414181636968976131126744027009648667545934567059936995464500558921628047976365686133316563907395703272034389175415267500915011198856872708848195531676931681272892143031376818016445477367518353497857924276463354162433601125960252109501612264110346083465648235597934274056868849224458745493776752120324703803035491157544831295275891939893680876327685438769557694881422844311998595700727521393176837831770339130423060958999137314684569010422095161967070506420256733873446115655276175992727151877660010238944760539789516945708802728736225121076224091810066700883474737605156285533943565843756271241244457651663064085939507947550920463932245202535463634444791755661725962187199279186575490857852950012840229035061514937310107009446151011613712423761426722541732055959202782129325725947146417224977321316381845326555279604270541871496236585252458648933254145062642337885651464670604298564781968461593663288954299780722542264790400616019751975007460545150060291806638271497016110987951336633771378434416194053121445291855180136575558667615019373029691932076120009255065081583275508499340768797252369987023567931026804136745718956641431852679054717169962990363015545645090044802789055701968328313630718997699153166679208958768572290600915472919636381673596673959975710326015571920237348580521128117458610065152598883843114511894880552129145775699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156736L}

Answer 5

J: -23 (77-50*2)

This doesn't work for n<=2 yet, not sure why. I'll look into fixing this, but if anyone knows an anwer, please say so in the comments.

~.>.|"."1 k,~"1 k,"1((,~(,&k=:'x',~":k))~)/"1((5^n),n)$;{;/(n=:n-1)#,:'*%+-^'

Answer 6

Haskell, 35

I'm not sure whether a function is enough or an actual program is required, so I'm posting two versions, both with 100 bonus.

As a program, score of 80:

import Data.List
d x=[flip x,x]
n#1=[n]
n#k=[(+),(-),(*),(/),(**)]>>=d>>=($n#(k-1)).map.($n)
g[n,k]=filter(>0)$[1..read k::Int]>>=map floor.(read n#)
main=interact$show.nub.g.words

or as a function, score of 35:

import Data.List
d x=[flip x,x]
n#1=[n]
n#k=[(+),(-),(*),(/),(**)]>>=d>>=($n#(k-1)).map.($n)
n%k=nub.filter(>0)$[1..k]>>=map floor.(n#)

sample output, for (4%3) or echo 4 3|codegolf.exe, sorted for your conveneince:

[1,2,3,4,5,8,12,16,20,32,64,252,256,260,1024,4096,65536,4294967296,13407807929942597099574024998205846127479365820592393
377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096,17976931348623159
077293051907890247336179769789423065727343008115773267580550096313270847732240753602112011387987139335765878976881441662
249284743063947412437776789342486548527630221960124609411945308295208500576883815068234246288147391311054082723716335051
0684586298239947245938479716304835356329624224137216]

The only thing that is a little weird about this is that the floating-point number Infinity floors to a humongous integer, but I hope this doesn't matter too much.

Answer 7

J, -43 (53-2*50)

[:~.[:<.[:|[:;(#~&x:)4 :'y/x'L:1[:([:{(<<"0'-+%*^')#~<:)]

This doesn't always work, because J tries to prevent calculations with numbers that are too large. If we are allowed to use (machine) floats, which simply get set to infinity on an overflow, we get the following, slightly shorter, for a score of 52-100 = -48:

[:~.[:<.[:|[:;#~4 :'y/x'L:1[:([:{(<<"0'-+%*^')#~<:)]

This is a version not in any way shape or from inspired by my previous J answer, so I'm posting it as a separate answer. Trivia: this might be the first time I've had to use an explicit function in a J answer.

Usage (Yes, the little boxes are actual data structures in J, and are actually displayed like this.):

   f =: [:~.[:<.[:|[:;(#~&x:)4 :'y/x'L:1[:([:{(<<"0'-+%*^')#~<:)]
   g =: [:~.[:<.[:|[:;#~4 :'y/x'L:1[:([:{(<<"0'-+%*^')#~<:)]
   test =: (/:~ L: 0) @: (g ; f) f. NB. Make a list of the result of both functions, and sort the answers.

   5!:4 <'f'
  ┌─ [:                                                                 
  ├─ ~.                                                                 
  │    ┌─ [:                                                            
──┤    ├─ <.                                                            
  │    │    ┌─ [:                                                       
  └────┤    ├─ |                                                        
       │    │    ┌─ [:                                                  
       └────┤    ├─ ;                                                   
            │    │           ┌─ ~ ─── #                                 
            │    │    ┌─ & ──┴─ x:                                      
            └────┤    │            ┌─ 4                                 
                 │    │      ┌─ : ─┴─ ,:'y/x'                           
                 │    ├─ L: ─┴─ 1                                       
                 └────┤                                                 
                      │      ┌─ [:                                      
                      │      │     ┌─ [:                                
                      │      │     ├─ {                                 
                      └──────┼─────┤         ┌─ <'-';'+';'%';'*';'^'    
                             │     └─────────┼─ ~ ──────────────────── #
                             │               └─ <:                      
                             └─ ]                                       

   2 test 2
┌─────┬─────┐
│0 1 4│0 1 4│
└─────┴─────┘
   4 test 3
┌────────────────────────────────────────────────────────────────┬──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
│0 1 3 4 5 12 20 32 64 252 260 1024 65536 4.29497e9 1.34078e154 _│0 1 3 4 5 12 20 32 64 252 260 1024 65536 4294967296 134078079299425970995740249982058461274793658205923933777235614437217640300735469768018742981669034276900318581864860508537538828119465699...
└────────────────────────────────────────────────────────────────┴──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...

   /:~ 4 g 4 NB. _ is infinity in J.
0 1 2 3 4 5 7 8 9 12 16 20 24 28 36 48 60 64 68 80 128 248 256 264 1008 1020 1024 1028 1040 4096 65532 65540 262144 1.67772e7 4.29497e9 4.29497e9 1.71799e10 1.09951e12 1.84467e19 3.40282e38 1.34078e154 5.36312e154 3.4324e156 _
   4 f 4
|limit error
|       y/x

Answer 8

Python 2 - 212 bytes (262-50)

Second ever code golf!

a,c,j=raw_input(),['+','-','*','/','**'],set()
def e(f):
    for g in c:
        h=f.replace('.',g,1)
        if '.' in h:e(h)
        else:
            i=eval(h)
            if i>=0:j.add(i)
for d in range(1,input()+1):e(((a+'.')*d)[:d*2-1])
print(j)

EDIT: Ok with brackets is gets a little larger:

With brackets - 354 bytes (404-50)

a,c,j=raw_input(),['+','-','*','/','**','+(','-(','*(','/(','**(',')+',')-',')*',')/',')**',')+(',')-(',')*(',')/(',')**(','(',')'],set()
def e(f):
    for g in c:
        h=f.replace('.',g,1)
        if '.' in h:e(h)
        else:
            try:
                i=eval(h)
                if i>=0:j.add(i)
            except:pass
for d in range(1,input()+1):e(((a+'.')*d)[:d*2-1])
print(j)

Answer 9

Haskell - 235 bytes - 100 bonus = 135

import Control.Monad
import Data.List (nub,sort)
r(l:h:_)=filter(>=0)$sort$nub$map(floor.foldr(\op m->n`op`m)n)$replicateM(k-1)[(+),(-),(*),(/),(**)]
 where n=fromIntegral l;k=fromIntegral h
main=interact(\s->show$r$map read$words s)

Tested with

$ printf "4 3" | ./pi
[0,1,3,4,5,12,20,32,64,260,1024,65536,4294967296,13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096,179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216]

This result is achieved using replicateM. If we use the input 4 3, replicateM will give us the following arrays of functions : [[(+),(+)],[(+),(-)],[(+),(*)],[(+),(/)],[(+),(**)],[(-),(+)],[(-),(-)],[(-),(*)],[(-),(/)],[(-),(**)],[(*),(+)],[(*),(-)],[(*),(*)],[(*),(/)],[(*),(**)],[(/),(+)],[(/),(-)],[(/),(*)],[(/),(/)],[(/),(**)],[(**),(+)],[(**),(-)],[(**),(*)],[(**),(/)],[(**),(**)]], or more simply, [[a->a->a]]. Each array is then folded from the right using n as input : [(+),(+)] = 4+(4+4) = 12. Note that there is no operator precedence here : [(*),(+)] = 4*(4+4) != (4*4)+4.

The given numbers are then floored, nubed, sorted and filtered for numbers less than 0.

Answer 10

C, dc & bash utils – 259 (source) + 21 (to run) - 100 bonuses = 180

Save as calc.c:

#include <stdio.h>
#define X printf
int main(int c,char*v[]){int n,k,l,t,i,j;char*O="+-*/^";if(c!=3)return 0;n=atoi(v[1]);k=atoi(v[2]);for(l=1,t=k;t>1;t--)l*=5;for(i=0;i<l;i++){t=i;X("%d ",n);for(j=1;j<k;j++){X("%d%c",n,O[t%5]);t/=5;}X("d*vp\n");}return 1;}

Compile:

gcc -o calc calc.c

This will output permutations of dc compatible input. dc is a unlimited precision calculator, so can generate large numbers, it also has exponentiation. dc in default mode uses integer arithmetic so that's floor builtin, and the common commands d*v near the end effectively take the absolute value to increase the number of possible valid outputs.

Running alone just generates a lot of output, e.g.

$ ./calc 6 2
6 6+d*vp
6 6-d*vp
6 6*d*vp
6 6/d*vp
6 6^d*vp

So to get the results, tie this into dc | sort -n | uniq | xargs to get the desired output, e.g.

$ ./calc 2 2 |dc|sort -n|uniq|xargs
0 1 4

$ ./calc 2 3 |dc|sort -n|uniq|xargs
0 1 2 3 6 8 16

$ ./calc 2 4 |dc|sort -n|uniq|xargs
0 1 2 3 4 5 6 8 9 10 12 14 16 18 32 36 64 256

$ ./calc 3 3 |dc|sort -n|uniq|xargs
0 1 2 3 4 6 9 12 18 24 27 30 81 216 729 19683

The highest k it can handle is 13, but then you'll be waiting a long time for the results!

$ ./calc 2 8 |dc|sort -n|uniq|xargs
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 56 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 87 88 92 94 95 96 97 98 99 100 101 102 104 106 108 110 112 114 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 136 138 140 142 143 144 145 146 148 150 152 154 156 158 159 160 161 162 163 164 165 166 167 168 169 170 171 180 190 192 194 195 196 197 198 199 200 201 202 204 206 208 223 224 225 227 238 240 242 244 246 248 250 252 253 254 255 256 257 258 259 260 262 264 266 268 272 280 282 284 286 287 288 289 290 291 292 294 296 304 310 311 312 313 314 316 318 320 322 323 324 325 326 328 330 332 338 359 361 363 364 384 386 388 390 391 392 393 394 396 398 400 402 404 408 441 448 449 450 451 452 480 482 484 486 496 500 502 504 506 508 509 510 511 512 513 514 515 516 518 520 522 524 527 528 529 531 544 568 572 574 576 577 578 579 580 584 621 623 624 625 627 629 640 642 644 645 646 647 648 649 650 651 652 654 656 674 676 678 720 721 722 723 724 727 729 731 776 780 782 784 786 788 792 796 798 800 802 804 841 896 898 900 902 904 959 961 963 968 1008 1012 1014 1016 1018 1020 1022 1023 1024 1025 1026 1028 1030 1032 1034 1036 1040 1058 1087 1089 1091 1148 1150 1152 1154 1156 1158 1160 1200 1225 1246 1248 1250 1252 1254 1288 1290 1292 1294 1295 1296 1297 1298 1300 1302 1304 1352 1369 1440 1442 1444 1446 1448 1458 1521 1564 1566 1568 1570 1572 1598 1600 1602 1640 1681 1764 1796 1798 1800 1802 1804 1920 1921 1922 1923 1924 1936 2032 2040 2042 2044 2045 2046 2047 2048 2049 2050 2051 2052 2054 2056 2064 2116 2176 2177 2178 2179 2180 2209 2302 2304 2306 2308 2310 2312 2314 2316 2399 2401 2403 2450 2498 2500 2502 2584 2586 2588 2590 2591 2592 2593 2594 2596 2598 2600 2601 2704 2738 2884 2886 2888 2890 2892 2916 3120 3134 3136 3138 3200 3278 3279 3280 3281 3282 3364 3444 3598 3600 3602 3840 3842 3844 3846 3848 3969 4088 4090 4092 4094 4095 4096 4097 4098 4100 4102 4104 4225 4352 4354 4356 4358 4360 4608 4622 4624 4626 4802 4898 4900 4902 4998 4999 5000 5001 5002 5041 5176 5180 5182 5184 5186 5188 5192 5202 5329 5474 5476 5478 5774 5776 5778 5929 6084 6239 6241 6243 6272 6400 6557 6559 6560 6561 6563 6565 6887 6889 6891 7200 7225 7320 7684 7686 7688 7690 7692 7938 8064 8184 8186 8188 8190 8191 8192 8193 8194 8196 8198 8200 8320 8450 8708 8710 8712 8714 8716 9216 9248 9409 9602 9604 9606 9800 9801 9996 9998 10000 10002 10004 10082 10364 10366 10367 10368 10369 10370 10372 10402 10404 10406 10658 10816 10952 11552 12482 12544 13118 13120 13122 13124 13126 13778 14161 14400 14639 14641 14643 14884 15129 15374 15376 15378 15625 15874 15876 15878 16127 16129 16131 16376 16380 16382 16383 16384 16385 16386 16388 16392 16639 16641 16643 16898 16900 16902 17161 17422 17424 17426 17956 18496 18818 19206 19207 19208 19209 19210 19600 19602 19996 19998 20000 20002 20004 20162 20164 20166 20732 20734 20736 20738 20740 20808 21314 21316 21318 21904 23104 24964 25600 25921 26242 26244 26246 26569 26896 27556 28561 29282 30752 31752 32256 32257 32258 32259 32260 32764 32765 32766 32767 32768 32769 32770 32771 32772 33280 33281 33282 33283 33284 33800 34848 36864 37634 37636 37638 38412 38414 38416 38418 38420 39202 39204 39206 39998 40000 40002 40328 40804 41468 41470 41472 41474 41476 41616 42632 50625 51842 52486 52487 52488 52489 52490 53138 58564 61504 62500 63502 63504 63506 64512 64514 64516 64518 64520 65025 65530 65532 65534 65535 65536 65537 65538 65540 65542 66049 66560 66562 66564 66566 66568 67598 67600 67602 68644 69696 75272 76828 76830 76832 76834 76836 78408 80000 80656 81796 82942 82944 82946 83521 84100 85264 97344 102400 103682 103684 103686 104972 104974 104976 104978 104980 106274 106276 106278 107584 127008 129028 129030 129032 129034 129036 130050 130321 131064 131066 131068 131070 131071 131072 131073 131074 131076 131078 131080 132098 133124 133126 133128 133130 133132 135200 150544 152100 153662 153664 153666 155236 156816 158404 159998 160000 160002 161604 165888 195312 202500 207368 209948 209950 209952 209954 209956 212552 234256 254016 256036 258062 258064 258066 260098 260100 260102 261121 262136 262140 262142 262144 262146 262148 262152 263169 264194 264196 264198 266254 266256 266258 268324 270400 279841 307328 320000 329476 331774 331776 331778 334084 388129 390623 390625 390627 393129 405000 414736 417316 418609 419902 419904 419906 421201 422500 425104 456976 516128 520200 521284 522242 524284 524286 524287 524288 524289 524290 524292 526338 528392 531441 532512 611524 614654 614656 614658 617796 640000 663552 668168 781250 806404 809998 810000 810002 813604 837218 839806 839807 839808 839809 839810 842402 923521 1032256 1040400 1042568 1044482 1044484 1044486 1048572 1048574 1048576 1048578 1048580 1052674 1052676 1052678 1056784 1065024 1185921 1229312 1327104 1331716 1336334 1336336 1336338 1340964 1562500 1620000 1669264 1674434 1674436 1674438 1679612 1679614 1679616 1679618 1679620 1684802 1684804 1684806 1690000 2079364 2085134 2085136 2085138 2088968 2090916 2097148 2097150 2097152 2097154 2097156 2105352 2458624 2560000 2672672 3240000 3348872 3359228 3359230 3359232 3359234 3359236 3369608 3694084 4170272 4177936 4186116 4190209 4194302 4194304 4194306 4198401 4202500 4210704 4743684 5308416 5345344 5764801 6250000 6697744 6708100 6718462 6718464 6718466 6728836 6739216 7388168 8340544 8380418 8388606 8388607 8388608 8388609 8388610 8396802 9487368 9834496 10758400 12960000 13436928 14760964 14776334 14776336 14776338 14791716 16744464 16760834 16760836 16760838 16777212 16777214 16777216 16777218 16777220 16793602 16793604 16793606 16810000 18957316 18974734 18974736 18974738 18992164 21381376 21523360 24010000 25000000 26853124 26873854 26873856 26873858 26894596 29552672 29986576 33362176 33521672 33554428 33554430 33554432 33554434 33554436 33587208 37949472 38950081 43020481 43046719 43046721 43046723 43072969 47458321 50000000 53747712 59105344 67043344 67076100 67108862 67108864 67108866 67141636 67174416 75898944 86093442 92236816 99960004 99999998 100000000 100000002 100040004 107495424 108243216 134217728 172186884 200000000 214358881 214990848 236421376 252047376 260144641 268369924 268435454 268435456 268435458 268500996 276922881 285610000 303595776 368947264 400000000 406586896 429898756 429981694 429981696 429981698 430064644 454371856 536870912 688747536 737894528 859963392 1040578564 1073610756 1073676289 1073741822 1073741824 1073741826 1073807361 1073872900 1107691524 1416468496 1475635396 1475789054 1475789056 1475789058 1475942724 1536953616 1600000000 1719926784 2081157128 2147352578 2147483646 2147483647 2147483648 2147483649 2147483650 2147614722 2215383048 2754990144 2951578112 4032758016 4162056196 4162314254 4162314256 4162314258 4162572324 4294443024 4294705154 4294705156 4294705158 4294967292 4294967294 4294967296 4294967298 4294967300 4295229442 4295229444 4295229446 4295491600 4430499844 4430766094 4430766096 4430766098 4431032356 4569760000 5509980288 5903156224 6879707136 8324628512 8589410312 8589934588 8589934590 8589934592 8589934594 8589934596 8590458888 8861532192 10750371856 11019540676 11019960574 11019960576 11019960578 11020380484 11294588176 16649257024 17178820624 17179344900 17179869182 17179869184 17179869186 17180393476 17180917776 17723064384 22039921152 23612624896 25600000000 34359738368 44079842304 66597028096 67652010000 68718428164 68719476734 68719476736 68719476738 68720525316 69799526416 70892257536 110075314176 137438953472 152587890625 176319369216 274877906944 377801998336 549755813888 656100000000 705277476864 1090946826256 1099507433476 1099511627774 1099511627776 1099511627778 1099515822084 1108126760976 1410554953728 1785793904896 2199023255552 2803735918096 2821103188996 2821109907454 2821109907456 2821109907458 2821116625924 2838564518416 4347792138496 4398046511104 5642219814912 11284439629824 17592186044416 45137758519296 70368744177664 140737488355328 218340105584896 280925623418896 281474909601796 281474976710654 281474976710656 281474976710658 281475043819524 282025135308816 360040606269696 562949953421312 722204136308736 1125899906842624 1853020188851841 4503599627370496 10000000000000000 72057594037927936 184884258895036416 1152921504606846976 2177953337809371136 4611686018427387904 9223372036854775808 17324859965700833536 18444492376972984336 18446744056529682436 18446744073709551614 18446744073709551616 18446744073709551618 18446744090889420804 18448995976604549136 19631688197463081216 36893488147419103232 73786976294838206464 121439531096594251776 295147905179352825856 4722366482869645213696 1208925819614629174706176 7958661109946400884391936 79228162514264337593543950336 340282366920938463463374607431768211456

Right now, it follows a strict # # op # op # op ... pattern, but you can get more numbers by switching the pattern around, e.g.:

(2 * 2 * 2) / (2 + 2) → 2 2 * 2 * 2 2 + /

The way this could be done is to treat the numbers and operators as symbols and permute them alike. You would get a lot of sequences not legal in dc, but let dc figure that out. Results pending...

Answer 11

HASKELL 98 (198-100 bonus)

edit: I'd comment, but I can't, I'd suggest to treat unlimited range as a bonus

It seems to me that a few answer miss a point: using at most k n. This means that f(4,3) can generate (4/4) = 1 or (4*4)=16.

Anyway that's my answer. I assume int/int to behave as floor. Exponentiation is included.

import Data.List
f=[(+),(-),div,(*),(^)]
a y f=f y
o n x=filter(>0).map(a n.a x)$f++map flip f
t[n,k]=(0:).nub.concat.take(fromInteger k)$iterate(>>=o n)[n]
main=interact$show.sort.t.map read.words

---

HASKELL 111 (211-100 bonus)

import Data.List
f=[(+),(-),div,(*),(^)]
c=concatMap
a y f=f y
o n x=map(a n.a x)$f++map flip f
l 1 _ s=0:s
l k o s=c(l(k-1)o.filter(>0))[c o s,s]
t[n,k]=l k(o n)[n]
main=interact$show.sort.nub.t.map read.words

Answer 12

Ruby 181 - 50 - 50 = 81

def p(k,n);k<=1?[n]:(1...k).reduce([]){|a,s|a+[:+,:-,:*,:/,:**].reduce([]){|a,o|b=p(s,n);b+a+b.product(p(k-s,n)).map{|a|a.reduce(&o) rescue nil}.compact}}.uniq.find_all{|k|k>=0};end