title: Convert Alpha-2 to Alpha-3

text:
# Question
Title: Convert Alpha-2 to Alpha-3
## The Task

The task is easy: given an Alpha-2 country code, output the Alpha-3 equivalent. The input may be in any case you choose, and the output in any consistent case of your choosing. Here are the codes:

```
[["AF", "AFG"], ["AX", "ALA"], ["AL", "ALB"], ["DZ", "DZA"], ["AS", "ASM"], ["AD", "AND"], ["AO", "AGO"], ["AI", "AIA"], ["AQ", "ATA"], ["AG", "ATG"], ["AR", "ARG"], ["AM", "ARM"], ["AW", "ABW"], ["AU", "AUS"], ["AT", "AUT"], ["AZ", "AZE"], ["BS", "BHS"], ["BH", "BHR"], ["BD", "BGD"], ["BB", "BRB"], ["BY", "BLR"], ["BE", "BEL"], ["BZ", "BLZ"], ["BJ", "BEN"], ["BM", "BMU"], ["BT", "BTN"], ["BO", "BOL"], ["BA", "BIH"], ["BW", "BWA"], ["BV", "BVT"], ["BR", "BRA"], ["VG", "VGB"], ["IO", "IOT"], ["BN", "BRN"], ["BG", "BGR"], ["BF", "BFA"], ["BI", "BDI"], ["KH", "KHM"], ["CM", "CMR"], ["CA", "CAN"], ["CV", "CPV"], ["KY", "CYM"], ["CF", "CAF"], ["TD", "TCD"], ["CL", "CHL"], ["CN", "CHN"], ["HK", "HKG"], ["MO", "MAC"], ["CX", "CXR"], ["CC", "CCK"], ["CO", "COL"], ["KM", "COM"], ["CG", "COG"], ["CD", "COD"], ["CK", "COK"], ["CR", "CRI"], ["CI", "CIV"], ["HR", "HRV"], ["CU", "CUB"], ["CY", "CYP"], ["CZ", "CZE"], ["DK", "DNK"], ["DJ", "DJI"], ["DM", "DMA"], ["DO", "DOM"], ["EC", "ECU"], ["EG", "EGY"], ["SV", "SLV"], ["GQ", "GNQ"], ["ER", "ERI"], ["EE", "EST"], ["ET", "ETH"], ["FK", "FLK"], ["FO", "FRO"], ["FJ", "FJI"], ["FI", "FIN"], ["FR", "FRA"], ["GF", "GUF"], ["PF", "PYF"], ["TF", "ATF"], ["GA", "GAB"], ["GM", "GMB"], ["GE", "GEO"], ["DE", "DEU"], ["GH", "GHA"], ["GI", "GIB"], ["GR", "GRC"], ["GL", "GRL"], ["GD", "GRD"], ["GP", "GLP"], ["GU", "GUM"], ["GT", "GTM"], ["GG", "GGY"], ["GN", "GIN"], ["GW", "GNB"], ["GY", "GUY"], ["HT", "HTI"], ["HM", "HMD"], ["VA", "VAT"], ["HN", "HND"], ["HU", "HUN"], ["IS", "ISL"], ["IN", "IND"], ["ID", "IDN"], ["IR", "IRN"], ["IQ", "IRQ"], ["IE", "IRL"], ["IM", "IMN"], ["IL", "ISR"], ["IT", "ITA"], ["JM", "JAM"], ["JP", "JPN"], ["JE", "JEY"], ["JO", "JOR"], ["KZ", "KAZ"], ["KE", "KEN"], ["KI", "KIR"], ["KP", "PRK"], ["KR", "KOR"], ["KW", "KWT"], ["KG", "KGZ"], ["LA", "LAO"], ["LV", "LVA"], ["LB", "LBN"], ["LS", "LSO"], ["LR", "LBR"], ["LY", "LBY"], ["LI", "LIE"], ["LT", "LTU"], ["LU", "LUX"], ["MK", "MKD"], ["MG", "MDG"], ["MW", "MWI"], ["MY", "MYS"], ["MV", "MDV"], ["ML", "MLI"], ["MT", "MLT"], ["MH", "MHL"], ["MQ", "MTQ"], ["MR", "MRT"], ["MU", "MUS"], ["YT", "MYT"], ["MX", "MEX"], ["FM", "FSM"], ["MD", "MDA"], ["MC", "MCO"], ["MN", "MNG"], ["ME", "MNE"], ["MS", "MSR"], ["MA", "MAR"], ["MZ", "MOZ"], ["MM", "MMR"], ["NA", "NAM"], ["NR", "NRU"], ["NP", "NPL"], ["NL", "NLD"], ["AN", "ANT"], ["NC", "NCL"], ["NZ", "NZL"], ["NI", "NIC"], ["NE", "NER"], ["NG", "NGA"], ["NU", "NIU"], ["NF", "NFK"], ["MP", "MNP"], ["NO", "NOR"], ["OM", "OMN"], ["PK", "PAK"], ["PW", "PLW"], ["PS", "PSE"], ["PA", "PAN"], ["PG", "PNG"], ["PY", "PRY"], ["PE", "PER"], ["PH", "PHL"], ["PN", "PCN"], ["PL", "POL"], ["PT", "PRT"], ["PR", "PRI"], ["QA", "QAT"], ["RE", "REU"], ["RO", "ROU"], ["RU", "RUS"], ["RW", "RWA"], ["BL", "BLM"], ["SH", "SHN"], ["KN", "KNA"], ["LC", "LCA"], ["MF", "MAF"], ["PM", "SPM"], ["VC", "VCT"], ["WS", "WSM"], ["SM", "SMR"], ["ST", "STP"], ["SA", "SAU"], ["SN", "SEN"], ["RS", "SRB"], ["SC", "SYC"], ["SL", "SLE"], ["SG", "SGP"], ["SK", "SVK"], ["SI", "SVN"], ["SB", "SLB"], ["SO", "SOM"], ["ZA", "ZAF"], ["GS", "SGS"], ["SS", "SSD"], ["ES", "ESP"], ["LK", "LKA"], ["SD", "SDN"], ["SR", "SUR"], ["SJ", "SJM"], ["SZ", "SWZ"], ["SE", "SWE"], ["CH", "CHE"], ["SY", "SYR"], ["TW", "TWN"], ["TJ", "TJK"], ["TZ", "TZA"], ["TH", "THA"], ["TL", "TLS"], ["TG", "TGO"], ["TK", "TKL"], ["TO", "TON"], ["TT", "TTO"], ["TN", "TUN"], ["TR", "TUR"], ["TM", "TKM"], ["TC", "TCA"], ["TV", "TUV"], ["UG", "UGA"], ["UA", "UKR"], ["AE", "ARE"], ["GB", "GBR"], ["US", "USA"], ["UM", "UMI"], ["UY", "URY"], ["UZ", "UZB"], ["VU", "VUT"], ["VE", "VEN"], ["VN", "VNM"], ["VI", "VIR"], ["WF", "WLF"], ["EH", "ESH"], ["YE", "YEM"], ["ZM", "ZMB"], ["ZW", "ZWE"]]

```

## Test Cases

```
US -> USA
GT -> GTM
VA -> VAT
IN -> IND
KP -> PRK

```

## Scoring

Because my soft drive can only store a kilobyte, and because this is , the shortest code in bytes wins.

This is the reverse of this challenge.

# Answer
> 5 votes
# JavaScript (ES6),  ~~582~~  554 bytes

```
s=>("CCAPMSSS"[x="KYKMTFKPYTPMRSGSAXAQBYBJBAMOEEGWIEILSIUA".search([a,b]=s)/2]||a)+("YOTRYPRGLTLEIASNRSVK"[x]+"MMFKTMBSAARNHCTBLRNR"[x]||(c="E8bOUX3b11R1O1nadL2DIRG1ntTRlSdIeSo10M1L1RK2C2D2RL1U2i4L22N23N3RynL2ao1c3IEr2l1r11T39U9U5S15UlyNw1PN1MvEReM2uDP1l2Rw13c2O2KLSkuN2u1O1uN25I11rB10T1T1N1B1R4M6TnrGt4BrTg2GMuS1bl1E10Mr1gL1RRd2MUrL3hN1T3l10N1Ko1aoEV1ohRhL2I2BpMRPE14U4In3M3F11B7U1E1Ys9IPH24NIl1s1r21BR1rOuY1B2rBi1lnC1MM3u21G1DD3V1IN18N8NDT1rNL21Y7a1RN24N1ZMR8o4T2a10ON1".replace(/\d+/g,n=>"A".repeat(n))[parseInt(s,36)%774],c>{}?c.toUpperCase()+b:b+c))

```

Try it online!

### How?

The most common letter that needs to be added to an alpha-2 code to get the alpha-3 code is `A`. Therefore, it's the best suited padding character for our main lookup string, which is expanded by replacing all integers with the corresponding number of `A`'s.

Try it online!

The lookup function is a single modulo on the input parsed in base-36:

```
parseInt(s, 36) % 774

```

If we get a character in upper case, it means that it must be added at the end of the alpha-2 code.

```
"AF" ~> "G" ~> "AF**G**"
```

If we get a character in lower case, it means that it must be added in the middle of the alpha-2 code:

```
"AO" ~> "g" ~> "A**G**O"
```

Similarly to my answer to the other challenge, the 20 codes that do not follow the above rules are hard-coded separately, just the other way around.

# Answer
> 4 votes
# Perl 5 `-MLocale::Country -pl`, ~~48~~ 40 bytes

```
$_=country_code2code($_,,'alpha-3')||ant

```

Try it online!

For some reason, the AN-\>ANT mapping isn't in Perl's list so I had to hardcode it.

# Answer
> 3 votes
# 05AB1E, ~~435~~ ~~426~~ 422 bytes

```
.•4₆₆ÿ¸˜E¡´³*ιœýOóÖq₅;YpÂ-|ož®Ωg4∊₅“=à–ô9αA$ΔL,žÆE6óµQ£‚Ç\ΣN¬ÓóÑC∞\†ìвö—'‰ßÍ™¶HFü"í4·nÛZ0ø₅k{'¦Δ"¢h¦h)U–Ì±4ƒ¿¢
œ\a^»ãfzλ»Ï˜≠7>2e5Nl”SGed.iÉVó¸£₃l&C§ÚΣ6½+¢ å(₃L¦Ûā:vÊιOL†aëƵ₁fǝfVEtþΣ{õ-o¡ø4•u2ôD•46‰εcĆ2Zâæ¥ÙÚMт'•₂в£εN>.b«}˜ø.•1…¤θ30ËиʒÕf%γžBpéт(ĆVáä∞Kî%àôλ#KbÉµC‘jÊα-zª+UΛGÙÀ"zFûÌιô#fиαL¸Λ¾o₄Ò{žwým«‚È3÷«εΩ)ØN÷U•u2ôD•Gò7¬ýà®vQ<ÑU•12в£ε€SN>.bý}˜áø.•Úù»ÔáÝâ|¹мœ4å)Çø{:вoÒaÿšмk*øW—Ã*‹ΣcÌ‰Δú¤š3rSwsJÜ²ùη₅ĀPŽEf~:•u23S40∍£)˜DIk>è

```

Try it online or verify all test cases.

**Explanation:**

Step 1a: Create I/O pairs of all alpha-2 codes for which a single trailing letter has to be added for the alpha-3 conversion:

```
.•4₆₆ÿ¸˜E¡´³*ιœýOóÖq₅;YpÂ-|ož®Ωg4∊₅“=à–ô9αA$ΔL,žÆE6óµQ£‚Ç\ΣN¬ÓóÑC∞\†ìвö—'‰ßÍ™¶HFü"í4·nÛZ0ø₅k{'¦Δ"¢h¦h)U–Ì±4ƒ¿¢
œ\a^»ãfzλ»Ï˜≠7>2e5Nl”SGed.iÉVó¸£₃l&C§ÚΣ6½+¢ å(₃L¦Ûā:vÊιOL†aëƵ₁fǝfVEtþΣ{õ-o¡ø4•
              "# Push compressed string "dzaibwbrbfdmfrghitlvmdngrwknlclktzthtcugusalvgcugagmgiuzzmgrnihmhninmknlssazczlipsslchzwzaafarhkmnetcrdjerfjhtmwmlprumccnftjbebocoismhnpncnzphtkaskhdogugtnablwssosjvnyebtcafihuidirimjpkelbompashsdtwtovegelalsmctgttcystsgesbhbgcmcxjokimsmammnenopesmsygbviaumymurutlbviovakwmranqavcvubmecdeltnrrerosacihrluegggjekg"
 u             # Uppercase it
  2ô           # Split it into parts of size 2
    D          # Duplicate this list of pairs
•46‰εcĆ2Zâæ¥ÙÚMт'•
              '# Push compressed integer 5045888909142307005039435397419896531
 ₂в            # Convert it to base-26 as list: [21,8,2,6,7,1,4,1,9,0,3,10,12,17,6,4,0,16,5,9,8,2,0,1,3,1]
   £           # Split the duplicated pairs into parts of that size
    ε          # Map over each list of string-pairs:
     N>        #  Push the 1-based map-index
       .b      #  Convert it to an uppercase alphabetic letter (1=A,2=B,...,26=Z)
         «     #  Append it to each string-pair in the current list
    }˜         # After the map: flatten
      ø        # Create pairs of the two lists

```

Try just this step, to see all I/O pairs of step 1a.

Step 1b: Create I/O pairs of all alpha-2 codes for which a single middle letter has to be added for the alpha-3 conversion:

```
.•1…¤θ30ËиʒÕf%γžBpéт(ĆVáä∞Kî%àôλ#KbÉµC‘jÊα-zª+UΛGÙÀ"zFûÌιô#fиαL¸Λ¾o₄Ò{žwým«‚È3÷«εΩ)ØN÷U•
               # Push compressed string "cfjmkzpkmfawlrlytdpnbimgmvmxsnaobdbsclcngnnutmbzsvfkgpmtpwsbwfaddkgqmemppgcgcdckkrmzplcvambbbnfoglgdiqpyptaeuyfmehagmqatgfgysrtntrtvskszsepfsc"
 u2ôD          # Same as above (uppercase; split into pairs; duplicate)
•Gò7¬ýà®vQ<ÑU• # Push compressed integer 5023299766197034891137684120
 12в           # Convert it to base-12 as list: [5,3,2,3,2,0,2,3,2,0,1,8,0,6,6,1,0,11,2,2,7,1,2,0,2,0]
    £          # Split the duplicated pairs into parts of that size
     ε         # Map over each list of string-pairs:
      €S       #  Convert each string to a list
        N>.b   #  Same as above: get the uppercase letter based on the index
            ý  #  Join the inner list-pairs with this letter as delimiter
     }˜áø      # Same as above, but `á` removes empty strings from the list

```

Try just this step, to see all I/O pairs of step 1b.

Step 1c: Create I/O pairs for all remaining alpha-2 to alpha-3 conversions (as a flattened list):

```
.•Úù»ÔáÝâ|¹мœ4å)Çø{:вoÒaÿšмk*øW—Ã*‹ΣcÌ‰Δú¤š3rSwsJÜ²ùη₅ĀPŽEf~:•
               # Push compressed string "aqataaxalababihbjbenbyblreeestgssgsgwgnbieirlilisrkmcomkpprkkycymmomacpmspmrssrbsisvntfatfuaukrytmyt"
 u             # Uppercase it
  23S          # Push [2,3]
     40∍       # Extend it to size 40: [2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3]
        £      # Split the string into parts of that size

```

Try just this step, to see the flattened list of all the I/O pairs of step 1c.

Step 2: Combine the results of the previous steps, and use them for the input to output conversion:

```
)              # Wrap the entire stack into a list
 ˜             # Flatten
  D            # Duplicate this list
   Ik          # Get the index of the input-string
     >         # Increase this index by 1
      è        # And use it to index into the list
               # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (sections *How to compress strings not part of the dictionary?*, *How to compress large integers?*, and *How to compress integer lists?*) to understand how the compressions work.

# Answer
> 3 votes
# , 74 bytes

```
function(c)`if`(c=="AN","ANT",countrycode::countrycode(c,"iso2c","iso3c"))

```

Try it rdrr.io!

# Answer
> 2 votes
# Python 1779 bytes

```
a=' AF AFG AX ALA AL ALB DZ DZA AS ASM AD AND AO AGO AI AIA AQ ATA AG ATG AR ARG AM ARM AW ABW AU AUS AT AUT AZ AZE BS BHS BH BHR BD BGD BB BRB BY BLR BE BEL BZ BLZ BJ BEN BM BMU BT BTN BO BOL BA BIH BW BWA BV BVT BR BRA VG VGB IO IOT BN BRN BG BGR BF BFA BI BDI KH KHM CM CMR CA CAN CV CPV KY CYM CF CAF TD TCD CL CHL CN CHN HK HKG MO MAC CX CXR CC CCK CO COL KM COM CG COG CD COD CK COK CR CRI CI CIV HR HRV CU CUB CY CYP CZ CZE DK DNK DJ DJI DM DMA DO DOM EC ECU EG EGY SV SLV GQ GNQ ER ERI EE EST ET ETH FK FLK FO FRO FJ FJI FI FIN FR FRA GF GUF PF PYF TF ATF GA GAB GM GMB GE GEO DE DEU GH GHA GI GIB GR GRC GL GRL GD GRD GP GLP GU GUM GT GTM GG GGY GN GIN GW GNB GY GUY HT HTI HM HMD VA VAT HN HND HU HUN IS ISL IN IND ID IDN IR IRN IQ IRQ IE IRL IM IMN IL ISR IT ITA JM JAM JP JPN JE JEY JO JOR KZ KAZ KE KEN KI KIR KP PRK KR KOR KW KWT KG KGZ LA LAO LV LVA LB LBN LS LSO LR LBR LY LBY LI LIE LT LTU LU LUX MK MKD MG MDG MW MWI MY MYS MV MDV ML MLI MT MLT MH MHL MQ MTQ MR MRT MU MUS YT MYT MX MEX FM FSM MD MDA MC MCO MN MNG ME MNE MS MSR MA MAR MZ MOZ MM MMR NA NAM NR NRU NP NPL NL NLD AN ANT NC NCL NZ NZL NI NIC NE NER NG NGA NU NIU NF NFK MP MNP NO NOR OM OMN PK PAK PW PLW PS PSE PA PAN PG PNG PY PRY PE PER PH PHL PN PCN PL POL PT PRT PR PRI QA QAT RE REU RO ROU RU RUS RW RWA BL BLM SH SHN KN KNA LC LCA MF MAF PM SPM VC VCT WS WSM SM SMR ST STP SA SAU SN SEN RS SRB SC SYC SL SLE SG SGP SK SVK SI SVN SB SLB SO SOM ZA ZAF GS SGS SS SSD ES ESP LK LKA SD SDN SR SUR SJ SJM SZ SWZ SE SWE CH CHE SY SYR TW TWN TJ TJK TZ TZA TH THA TL TLS TG TGO TK TKL TO TON TT TTO TN TUN TR TUR TM TKM TC TCA TV TUV UG UGA UA UKR AE ARE GB GBR US USA UM UMI UY URY UZ UZB VU VUT VE VEN VN VNM VI VIR WF WLF EH ESH YE YEM ZM ZMB ZW ZWE'

z=lambda b:a[a.find(" "+b)+4:a.find(" "+b)+7]

```

Not sure what to do with the mass of data.

# Answer
> 2 votes
# Vyxal, 420 bytes

```
«⟑``‟Ḃȯ†√¦∑iRṫΠʁǓ₴5]p#4Ṅl}3ẋ¶T+⟑V]ḭr≤ṁǔ
A»cP⌐kẋṠ†⟇Ǔ≈ɽ⟩›ṪwSʀ₇⌊Ǔ∇•Xwð⇩I‡ṅfβ℅₍ṗµ∆€¾aǍ⟑Ȧ2⋏$λ⁺]/|f₁Pa⟨,₁,h¨ṁ₌ε⟑‹İ⟨Nṫw%yĖ⁼*>₈Ė¹ȯU÷s¬)∨ʀ0ŀƈ½)(m-Ẋ ǓḂ⟩[0e•₂↲S⟇Ġj⟨^ɖg[⌐₁⋏żo:ẎRʁ⌐ð%⇧↓Y*?* †8„S|⁽l3√⁺⟑«⇧2ẇ:»⟑⟇βE'ċ¬$≠∪₀↳↲æMf»₄τẇkA¨£vJfZ«ƛ¤‛H∧λŻJ@±*dCẋ°4£Mgċ ≥ƒX¢ǎd≤ǔ₈b¢&Ẋ≈•ġ.ẎAl>₅j¨∵½↳Ŀa>€¼₌Rǔb*JA⌐Ḃ∵Ḣ3\⌈|ẋ;Π1₆›Ẇ∧≬₆ETh□ʀ≬¨«⇧2ẇ:»½ǒ÷₇Π≤¶:ɽq∇¨»12τẇkAZƛ÷$f$vj;fZ«↲↵Ė¯≥꘍≠}ĊKṫ⟑ɖhṪ⁺|oI3⌈%‟ṙK/i⁺!ṅȮiȧS'₌βP⅛‛ṙ∧6ƈ;7↔⋎¡↵G]ḟɾḋ†*↑o«⇧23f20ẋfẇWf:⁰ḟ›i

```

Try it Online! or Verify all test cases (takes a while, but doesn't time out)

Messy port of 05AB1E.

## How?

```
«⟑``‟Ḃȯ†√¦∑iRṫΠʁǓ₴5]p#4Ṅl}3ẋ¶T+⟑V]ḭr≤ṁǔ
A»cP⌐kẋṠ†⟇Ǔ≈ɽ⟩›ṪwSʀ₇⌊Ǔ∇•Xwð⇩I‡ṅfβ℅₍ṗµ∆€¾aǍ⟑Ȧ2⋏$λ⁺]/|f₁Pa⟨,₁,h¨ṁ₌ε⟑‹İ⟨Nṫw%yĖ⁼*>₈Ė¹ȯU÷s¬)∨ʀ0ŀƈ½)(m-Ẋ ǓḂ⟩[0e•₂↲S⟇Ġj⟨^ɖg[⌐₁⋏żo:ẎRʁ⌐ð%⇧↓Y*?* †8„S|⁽l3√⁺⟑«
                            # Push compressed string "dzaibwbrbfdmfrghitlvmdngrwknlclktzthtcugusalvgcugagmgiuzzmgrnihmhninmknlssazczlipsslchzwzaafarhkmnetcrdjerfjhtmwmlprumccnftjbebocoismhnpncnzphtkaskhdogugtnablwssosjvnyebtcafihuidirimjpkelbompashsdtwtovegelalsmctgttcystsgesbhbgcmcxjokimsmammnenopesmsygbviaumymurutlbviovakwmranqavcvubmecdeltnrrerosacihrluegggjekg"
⇧                           # Uppercase
 2ẇ                         # Split into chunks of two
   :                        # Duplicate
    »⟑⟇βE'ċ¬$≠∪₀↳↲æMf»      # Push compressed integer 5045888909142307005039435397419896531
                      ₄τ    # Convert to base-26 as a list: [21,8,2,6,7,1,4,1,9,0,3,10,12,17,6,4,0,16,5,9,8,2,0,1,3,1]
                        ẇ   # Split the string into chunks of that size: [["DZ", "AI", ..., "US"], ["AL", "VG", ..., "ZM"], ["GR", "NI"], ..., ["KG"]]
kA                          # Push the uppercase alphabet
  ¨£vJ                      # Zip the list with the alphabet, and for each, append the corresponding letter to each:
                            #  [["DZA", "AIA", ..., "USA"], ["ALB", "VGB", ..., "ZMB"], ["GRC", "NIC"], ..., ["KGZ"]]
      f                     # Flatten
       Z                    # Zip the ["DZ", "AI", "BW", ...] list with this
«ƛ¤‛H∧λŻJ@±*dCẋ°4£Mgċ ≥ƒX¢ǎd≤ǔ₈b¢&Ẋ≈•ġ.ẎAl>₅j¨∵½↳Ŀa>€¼₌Rǔb*JA⌐Ḃ∵Ḣ3\⌈|ẋ;Π1₆›Ẇ∧≬₆ETh□ʀ≬¨«
                            # Push compressed string "cfjmkzpkmfawlrlytdpnbimgmvmxsnaobdbsclcngnnutmbzsvfkgpmtpwsbwfaddkgqmemppgcgcdckkrmzplcvambbbnfoglgdiqpyptaeuyfmehagmqatgfgysrtntrtvskszsepfsc"
        ⇧2ẇ                 # Uppercase and split into chunks of two
           :                # Duplicate
            »½ǒ÷₇Π≤¶:ɽq∇¨»  # Push compressed integer 5023299766197034891137684120
12τ                         # Convert to base 12 as a list: [5,3,2,3,2,0,2,3,2,0,1,8,0,6,6,1,0,11,2,2,7,1,2,0,2,0]
   ẇ                        # Split the list into chunks of that size: [["CF", "JM", "KZ", "PK", "MF"], ["AW", "LR", "LY"], ..., ["PF", "SC"], []]
    kAZ                     # Zip with the uppercase alphabet
       ƛ÷$f$vj;             # Map, and for each, insert the letter between each string: [["CAF", "JAM", "KAZ", "PAK", "MAF"], ..., ["PYF", "SYC"], []]
               fZ           # Flatten and zip the ["CF", "JM", ..., "SC"] list with this
«↲↵Ė¯≥꘍≠}ĊKṫ⟑ɖhṪ⁺|oI3⌈%‟ṙK/i⁺!ṅȮiȧS'₌βP⅛‛ṙ∧6ƈ;7↔⋎¡↵G]ḟɾḋ†*↑o«
                            # Push compressed string "aqataaxalababihbjbenbyblreeestgssgsgwgnbieirlilisrkmcomkpprkkycymmomacpmspmrssrbsisvntfatfuaukrytmyt"
⇧                           # Uppercase
 23f                        # Push list [2, 3]
    20ẋf                    # Repeat it twenty times: [2, 3, 2, 3, 2, 3, ..., 2, 3]
        ẇ                   # Split the string into chunks of that size: ["AQ", "ATA", "AX", ..., "YT", "MYT"]
         W                  # Wrap the stack into a list
          f                 # Flatten
           :                # Duplicate
            ⁰ḟ              # Find the index of the input in it
              ›             # Increment
               i            # Index into the list

```

# Answer
> 1 votes
# C - 1324 Bytes

```
char*c="AFAFGAXALAALALBDZDZAASASMADANDAOAGOAIAIAAQATAAGATGARARGAMARMAWABWAUAUSATAUTAZAZEBSBHSBHBHRBDBGDBBBRBBYBLRBEBELBZBLZBJBENBMBMUBTBTNBOBOLBABIHBWBWABVBVTBRBRAVGVGBIOIOTBNBRNBGBGRBFBFABIBDIKHKHMCMCMRCACANCVCPVKYCYMCFCAFTDTCDCLCHLCNCHNHKHKGMOMACCXCXRCCCCKCOCOLKMCOMCGCOGCDCODCKCOKCRCRICICIVHRHRVCUCUBCYCYPCZCZEDKDNKDJDJIDMDMADODOMECECUEGEGYSVSLVGQGNQERERIEEESTETETHFKFLKFOFROFJFJIFIFINFRFRAGFGUFPFPYFTFATFGAGABGMGMBGEGEODEDEUGHGHAGIGIBGRGRCGLGRLGDGRDGPGLPGUGUMGTGTMGGGGYGNGINGWGNBGYGUYHTHTIHMHMDVAVATHNHNDHUHUNISISLININDIDIDNIRIRNIQIRQIEIRLIMIMNILISRITITAJMJAMJPJPNJEJEYJOJORKZKAZKEKENKIKIRKPPRKKRKORKWKWTKGKGZLALAOLVLVALBLBNLSLSOLRLBRLYLBYLILIELTLTULULUXMKMKDMGMDGMWMWIMYMYSMVMDVMLMLIMTMLTMHMHLMQMTQMRMRTMUMUSYTMYTMXMEXFMFSMMDMDAMCMCOMNMNGMEMNEMSMSRMAMARMZMOZMMMMRNANAMNRNRUNPNPLNLNLDANANTNCNCLNZNZLNINICNENERNGNGANUNIUNFNFKMPMNPNONOROMOMNPKPAKPWPLWPSPSEPAPANPGPNGPYPRYPEPERPHPHLPNPCNPLPOLPTPRTPRPRIQAQATREREUROROURURUSRWRWABLBLMSHSHNKNKNALCLCAMFMAFPMSPMVCVCTWSWSMSMSMRSTSTPSASAUSNSENRSSRBSCSYCSLSLESGSGPSKSVKSISVNSBSLBSOSOMZAZAFGSSGSSSSSDESESPLKLKASDSDNSRSURSJSJMSZSWZSESWECHCHESYSYRTWTWNTJTJKTZTZATHTHATLTLSTGTGOTKTKLTOTONTTTTOTNTUNTRTURTMTKMTCTCATVTUVUGUGAUAUKRAEAREGBGBRUSUSAUMUMIUYURYUZUZBVUVUTVEVENVNVNMVIVIRWFWLFEHESHYEYEMZMZMBZWZWE";f(char* i){for(;*c;c+=5)!strncmp(c, i,2)&&printf("%c%c%c",*(c+2),*(c+3),*(c+4));}

```

**Ungolfed**

```
char*c = "AFAFGAXALAALALBDZDZAASASMADANDAOAGOAIAIAAQATAAGATGARARGAMARMAWABWAUAUSATAUTAZAZEBSBHSBHBHRBDBGDBBBRBBYBLRBEBELBZBLZBJBENBMBMUBTBTNBOBOLBABIHBWBWABVBVTBRBRAVGVGBIOIOTBNBRNBGBGRBFBFABIBDIKHKHMCMCMRCACANCVCPVKYCYMCFCAFTDTCDCLCHLCNCHNHKHKGMOMACCXCXRCCCCKCOCOLKMCOMCGCOGCDCODCKCOKCRCRICICIVHRHRVCUCUBCYCYPCZCZEDKDNKDJDJIDMDMADODOMECECUEGEGYSVSLVGQGNQERERIEEESTETETHFKFLKFOFROFJFJIFIFINFRFRAGFGUFPFPYFTFATFGAGABGMGMBGEGEODEDEUGHGHAGIGIBGRGRCGLGRLGDGRDGPGLPGUGUMGTGTMGGGGYGNGINGWGNBGYGUYHTHTIHMHMDVAVATHNHNDHUHUNISISLININDIDIDNIRIRNIQIRQIEIRLIMIMNILISRITITAJMJAMJPJPNJEJEYJOJORKZKAZKEKENKIKIRKPPRKKRKORKWKWTKGKGZLALAOLVLVALBLBNLSLSOLRLBRLYLBYLILIELTLTULULUXMKMKDMGMDGMWMWIMYMYSMVMDVMLMLIMTMLTMHMHLMQMTQMRMRTMUMUSYTMYTMXMEXFMFSMMDMDAMCMCOMNMNGMEMNEMSMSRMAMARMZMOZMMMMRNANAMNRNRUNPNPLNLNLDANANTNCNCLNZNZLNINICNENERNGNGANUNIUNFNFKMPMNPNONOROMOMNPKPAKPWPLWPSPSEPAPANPGPNGPYPRYPEPERPHPHLPNPCNPLPOLPTPRTPRPRIQAQATREREUROROURURUSRWRWABLBLMSHSHNKNKNALCLCAMFMAFPMSPMVCVCTWSWSMSMSMRSTSTPSASAUSNSENRSSRBSCSYCSLSLESGSGPSKSVKSISVNSBSLBSOSOMZAZAFGSSGSSSSSDESESPLKLKASDSDNSRSURSJSJMSZSWZSESWECHCHESYSYRTWTWNTJTJKTZTZATHTHATLTLSTGTGOTKTKLTOTONTTTTOTNTUNTRTURTMTKMTCTCATVTUVUGUGAUAUKRAEAREGBGBRUSUSAUMUMIUYURYUZUZBVUVUTVEVENVNVNMVIVIRWFWLFEHESHYEYEMZMZMBZWZWE";

f(char* i)
{
    for(; *c; c += 5)
        !strncmp(c, i, 2) && printf("%c%c%c", *(c + 2), *(c + 3), *(c + 4));
}

```

**Explanation**

A function that receives a character string with an Alpha-2 code and converts it to Alpha-3 using a "raw" list which contains the Alpha-2 codes followed by their Alpha-3 counterpart every five(5) characters; the function looks for the given code within the list and if it is found its counterpart is displayed.

Tested on GCC, generates some warnings if not compiled with std=c89.

## C99 - 1296 Bytes (By @ceilingcat)

```
f(int*i){for(char*c="AFAFGAXALAALALBDZDZAASASMADANDAOAGOAIAIAAQATAAGATGARARGAMARMAWABWAUAUSATAUTAZAZEBSBHSBHBHRBDBGDBBBRBBYBLRBEBELBZBLZBJBENBMBMUBTBTNBOBOLBABIHBWBWABVBVTBRBRAVGVGBIOIOTBNBRNBGBGRBFBFABIBDIKHKHMCMCMRCACANCVCPVKYCYMCFCAFTDTCDCLCHLCNCHNHKHKGMOMACCXCXRCCCCKCOCOLKMCOMCGCOGCDCODCKCOKCRCRICICIVHRHRVCUCUBCYCYPCZCZEDKDNKDJDJIDMDMADODOMECECUEGEGYSVSLVGQGNQERERIEEESTETETHFKFLKFOFROFJFJIFIFINFRFRAGFGUFPFPYFTFATFGAGABGMGMBGEGEODEDEUGHGHAGIGIBGRGRCGLGRLGDGRDGPGLPGUGUMGTGTMGGGGYGNGINGWGNBGYGUYHTHTIHMHMDVAVATHNHNDHUHUNISISLININDIDIDNIRIRNIQIRQIEIRLIMIMNILISRITITAJMJAMJPJPNJEJEYJOJORKZKAZKEKENKIKIRKPPRKKRKORKWKWTKGKGZLALAOLVLVALBLBNLSLSOLRLBRLYLBYLILIELTLTULULUXMKMKDMGMDGMWMWIMYMYSMVMDVMLMLIMTMLTMHMHLMQMTQMRMRTMUMUSYTMYTMXMEXFMFSMMDMDAMCMCOMNMNGMEMNEMSMSRMAMARMZMOZMMMMRNANAMNRNRUNPNPLNLNLDANANTNCNCLNZNZLNINICNENERNGNGANUNIUNFNFKMPMNPNONOROMOMNPKPAKPWPLWPSPSEPAPANPGPNGPYPRYPEPERPHPHLPNPCNPLPOLPTPRTPRPRIQAQATREREUROROURURUSRWRWABLBLMSHSHNKNKNALCLCAMFMAFPMSPMVCVCTWSWSMSMSMRSTSTPSASAUSNSENRSSRBSCSYCSLSLESGSGPSKSVKSISVNSBSLBSOSOMZAZAFGSSGSSSSSDESESPLKLKASDSDNSRSURSJSJMSZSWZSESWECHCHESYSYRTWTWNTJTJKTZTZATHTHATLTLSTGTGOTKTKLTOTONTTTTOTNTUNTRTURTMTKMTCTCATVTUVUGUGAUAUKRAEAREGBGBRUSUSAUMUMIUYURYUZUZBVUVUTVEVENVNVNMVIVIRWFWLFEHESHYEYEMZMZMBZWZWE";*c;c+=5)write(!strncmp(c,i,2),c+2,3);}

```

# Answer
> 1 votes
# Wolfram Language (Mathematica), 111 bytes

```
Switch[#,"HM","HMD","AN","ANT","PS","PSE",_,Association[#@"CountryCode"->#@"UNCode"&/@EntityList@"Country"]@#]&

```

Don't Try it online!

Try in the Wolfram Cloud!

---

Explanation:

`Switch[#,"HM","HMD","AN","ANT","PS","PSE",` If our input is equal to one of the three countries not in the Mathematica database, return the correct code.

`_,` Otherwise

`Association[#@"CountryCode"->#@"UNCode"&/@EntityList@"Country"]` Create an association between the two-letter and three-letter codes of each country

`@#]` and find the value matching the input.

# Answer
> 1 votes
# C, 216+554+1=771 bytes

```
#include<stdio.h>
#define G d=getc(f);w=d&31|64
FILE*f;char c,d,r[4],y,w;char*z(a,b){for(f=fopen("f","r");;){G;c=d/4&56;y=w;G;c|=d>>5&7;*r=a;r[1]=r[2]=b;r[c>26?1:2]=c&31|64;if(!c)fgets(r,4,f);if(a==y&b==w)return r;}}

```

It requires this file with the name "f" in the same directory, shown here as a hex dump. You can use `cut -c 11-58 "data.txt" | xxd -r -p > f` to recreate the file. It should have 554 bytes.

```
00000000  01 e6 01 18 41 4c 41 01  4c 04 3a 21 b3 a1 c4 81  |....ALA.L.:!....|
00000010  ef 01 29 01 11 41 54 41  c1 87 01 f2 c1 4d 81 57  |..)..ATA.....M.W|
00000020  41 75 c1 b4 01 ba a2 13  42 48 82 e4 c2 42 02 19  |Au......BH...B..|
00000030  42 4c 52 22 85 a2 9a 02  0a 42 45 4e 42 ad 22 d4  |BLR".....BENB.".|
00000040  22 8f 02 01 42 49 48 02  37 42 96 02 32 16 47 49  |"...BIH.7B..2.GI|
00000050  8f c2 4e 42 47 02 26 82  89 2b a8 43 4d 23 c1 c3  |..NBG.&..+.CM#..|
00000060  16 0b 19 43 59 4d 83 26  94 64 a3 0c a3 0e 08 eb  |...CYM.&.d......|
00000070  0d 0f 4d 41 43 43 58 23  63 23 8f 0b 0d 43 4f 4d  |..MACCX#c#...COM|
00000080  a3 e7 a3 e4 a3 eb 23 32  43 c9 48 d2 03 55 43 19  |......#2C.H..UC.|
00000090  03 ba a4 cb 24 2a 04 2d  24 af 45 a3 65 27 b3 96  |....$*.-$.E.e'..|
000000a0  a7 d1 25 32 05 05 45 53  54 25 14 a6 8b c6 4f 26  |..%2..EST%....O&|
000000b0  2a 26 c9 06 32 c7 a6 f0  26 14 06 41 54 46 07 41  |*&..2...&..ATF.A|
000000c0  07 4d 27 e5 44 a5 07 28  07 49 07 72 c7 4c c7 44  |.M'.D..(.I.r.L.D|
000000d0  a7 90 27 b5 27 b4 67 27  a7 2e 07 17 47 4e 42 c7  |..'.'.g'....GNB.|
000000e0  b9 28 34 08 8d 56 81 08  8e 28 d5 29 93 09 8e 29  |.(4..V...(.)...)|
000000f0  c4 29 d2 c9 51 09 05 49  52 4c 29 cd 09 0c 49 53  |.)..Q..IRL)...IS|
00000100  52 09 34 8a 2d 2a d0 6a  25 4a 4f 8b 3a 2b c5 4b  |R.4.-*.j%JO.:+.K|
00000110  49 0b 10 50 52 4b ab f2  4b 97 6b 47 2c e1 0c 36  |I..PRK..K.kG,..6|
00000120  2c c2 2c f3 8c 52 8c 59  0c a9 4c b4 6c 15 0d 8b  |,.,..R.Y..L.l...|
00000130  8d 87 2d 37 4d 79 8d 96  2d 2c ad 94 2d 88 cd 91  |..-7My..-,..-...|
00000140  4d 92 4d 75 19 14 4d 59  54 8d b8 c6 6d 0d 24 2d  |M.Mu..MYT...m.$-|
00000150  e3 0d ee ad c5 4d 53 4d  41 ad fa 4d 4d 2e a1 4e  |.....MSMA..MM..N|
00000160  b2 2e 90 0e 8c 41 8e 2e  83 2e 9a 0e 69 4e 45 0e  |.....A......iNE.|
00000170  27 ae 35 2e 66 ad d0 4e  4f 2f cd 90 2b b0 97 10  |'.5.f..NO/..+...|
00000180  b3 30 c1 b0 c7 d0 59 50  45 30 88 90 6e b0 ec d0  |.0....YPE0..n...|
00000190  54 30 32 51 81 52 a5 52  af 52 75 12 37 22 ac 33  |T02Q.R.R.Ru.7".3|
000001a0  c8 0b 2e 0c 23 8d 26 10  0d 53 50 4d 56 83 37 b3  |....#.&..SPMV.7.|
000001b0  53 4d 53 14 53 a1 93 ae  12 13 53 52 42 f3 23 13  |SMS.S.....SRB.#.|
000001c0  ac 53 07 d3 cb 13 09 53  56 4e b3 82 33 af 1a c1  |.S.....SVN..3...|
000001d0  07 13 53 47 53 13 93 45  13 0c 2b 33 c4 d3 b2 33  |..SGS..E..+3...3|
000001e0  aa d3 fa d3 e5 03 a8 53  59 34 d7 34 6a 14 3a 14  |.......SY4.4j.:.|
000001f0  28 54 6c 34 e7 34 8b 34  cf 34 f4 d4 ae d4 b2 b4  |(Tl4.4.4.4......|
00000200  6d 14 23 d4 b6 15 27 15  01 55 4b 52 c1 45 47 42  |m.#...'..UKR.EGB|
00000210  15 33 35 2d d5 59 15 5a  56 95 36 c5 36 ae 56 49  |.35-.Y.ZV.6.6.VI|
00000220  b7 86 c5 68 39 a5 1a 4d  1a b7                    |...h9..M..|
0000022a

```

The function takes the Alpha-2 code as two separate characters, which must be capitalized, and returns the capitalized Alpha-3 code. I don't know of an online compiler that allows you to include binary files like this, so no link, unfortunately.

#### Explanation:

Since we're only dealing with capital letters, we can use only the lower five bits to store a character. The basic strategy is to store the Alpha-2 codes in the file, and use the bits we save to describe how to create the Alpha-3 code; then, the program will search for the Alpha-2 code and follow the instructions.

The instruction format is simple. We have six instruction bits. The lower five bits store a 5-bit letter code which can be converted to ASCII with `&31|64`. If the high bit is zero, the letter is added to the end of the code. If it's one, the letter is inserted in the middle. If the instruction bits are all zero, the file stores the complete Alpha-3 code in the next 3 bytes of the file (these are visible in the hex dump).

Of the 247 conversions, 156 append a character to the end, 71 insert a character in the middle, 4 prepend a character to the beginning, and 16 conversions are replacements, which are anything not included in the other categories. Inserts and appends only use two bytes in the file, while the others use five; (156+71)\*2+(4+16)\*5=554 bytes.

Ungolfed version:

```
#include <stdio.h>
FILE* f;
char c,d,r[4],y,w;
char* z(a,b){
    for(f=fopen("f","r");;){
        // get first character
        d=getc(f); w=d&31|64;
        c=d/4&56;
        y=w;
        // get second character
        d=getc(f); w=d&31|64;
        c|=d>>5&7; // c now holds the instruction
        // prepare return string for inserts/appends
        r[0]=a;
        r[1]=r[2]=b;
        r[c>26?1:2]=c&31|64; // insert or append
        if(!c) // replace
            fgets(r,4,f);
        if(a==y&b==w)
            return r;
    }
}

```

---
Tags: code-golf, string
---


title: Divisible subset sums

text:
# Question
Title: Divisible subset sums
Inspired by the recent 3Blue1Brown video

Consider, for some positive integer \\$n\\$, the set \\$\\{1, 2, ..., n\\}\\$ and its subsets. For example, for \\$n = 3\\$, we have

$$\emptyset, \\{1\\}, \\{2\\}, \\{3\\}, \\{1,2\\}, \\{1,3\\}, \\{2,3\\}, \\{1,2,3\\}$$

If we take the sum of these subsets, we can then ask ourselves the following question:

> Of the sums of the subsets of \\$\\{1, 2, ..., n\\}\\$, how many are divisible by some given integer \\$k\\$?

Again, using \\$n = 3\\$ as an example, we have our subset sums as

$$0, 1, 2, 3, 3, 4, 5, 6$$

For \\$k = 2\\$, there are \\$4\\$ subsets whose sum is divisible by \\$k\\$: \\$\emptyset, \\{2\\}, \\{1,3\\}\\$ and \\$\\{1,2,3\\}\\$.

---

Given two positive integers \\$n \\$ and \\$k\\$, with \\$2 \le k \le n\\$, output the number of subsets of \\$\\{1, 2, 3, ..., n-1, n\\}\\$ such that their sum is divisible by \\$k\\$.

You may take input and give output in any reasonable manner and format. This is , so the shortest code in bytes wins.

---

## Test cases

```
   n    k    out
   3    2      4
   5    5      8
  13    8   1024
   2    2      2
   7    7     20
  14    4   4096
  15   10   3280
   9    5    104
   7    2     64
  11    4    512
  15    3  10944
  16    7   9364
  13    5   1640
  11    6    344
  12   10    410
   9    9     60

```

And, a couple of larger ones, taken from the approach in the 3Blue1Brown video:

```
 200, 5 -> 321387608851798055108392418468232520504440598757438176362496
2000, 5 -> 22962613905485090484656664023553639680446354041773904009552854736515325227847406277133189726330125398368919292779749255468942379217261106628518627123333063707825997829062456000137755829648008974285785398012697248956323092729277672789463405208093270794180999311632479761788925921124662329907232844394066536268833781796891701120475896961582811780186955300085800543341325166104401626447256258352253576663441319799079283625404355971680808431970636650308177886780418384110991556717934409897816293912852988275811422719154702569434391547265221166310540389294622648560061463880851178273858239474974548427800576

```

# Answer
# JavaScript (ES6), 40 bytes

Expects `(k)(n)`.

```
k=>g=(n,s=0)=>n--?g(n,s)+g(n,s-~n):s%k<1

```

Try it online!

### Commented

```
k =>           // outer function taking k
g = (          // inner recursive function taking:
  n,           //   n
  s = 0        //   s = sum of set entries
) =>           //
n-- ?          // if n is not equal to 0 (decrement it afterwards):
  g(n, s) +    //   do a recursive call with s unchanged
  g(n, s - ~n) //   do a recursive call where n+1 is added to s
:              // else:
  s % k < 1    //   increment the final result if k divides s

```
> 8 votes

# Answer
# Python 3, 54 bytes

```
f=lambda n,k,r=0:n and f(n-1,k,r)+f(n-1,k,r-n)or r%k<1

```

Try it online!
> 8 votes

# Answer
# PARI/GP, 34 bytes

```
f(n,k)=prod(i=1,n,x^i+1)%(x^k-1)%x
```

Attempt This Online!

## Longer but faster, 43 bytes:

```
f(n,k)=lift(prod(i=1,n,Mod(x^i+1,x^k-1)))%x
```

Attempt This Online!

Using generating functions. Finds the constant term of the polynomial \\$\prod\_{i=1}^n(X^i+1)\\$ in the ring \\$\mathbb{Z}\[X\]/((X^k-1))\\$.
> 5 votes

# Answer
# BQN, 26 bytes

`{+´0=|+´¨1+(⥊(↕2˘)/¨<)↕}`

This block takes *n* as its right argument and *k* as its left one

## Explanation:

```
    {
     +´                         # count (sum of booleans)
       0=|                     # values divisible by left argument (k)
            +´¨1+(⥊(↕2˘)/¨<)↕  # in the list of the sums of the subsets
                 (⥊(↕2˘)/¨<)    #   get all the subsets of
                            ↕  #   all natural integers inferior to the right argument (n)
            +´¨1+               #   +1 (otherwise values would go from 0 to (n-1) instead of the expected 1 to n)
                               }

```
> 5 votes

# Answer
# Vyxal `R`, 5 bytes

```
ṗṠ$Ḋ∑

```

Try it Online!

```
 Ṡ    # Sums of
ṗ     # Powersets of 1...input
  $Ḋ  # Are divisible by other input?
    ∑ # Count those where they are

```

# Vyxal `Rrs`, 3 bytes

```
ṗṠḊ

```

Try it Online!
> 4 votes

# Answer
# C (gcc), 79 bytes

```
a;p;s;b;f(n,k){for(a=b=0;++b<1<<n;a+=s%k<1)for(p=s=0;p<n;s+=1<<p++&b?p:0);++a;}

```

Try it online!

### Port of Arnauld's JavaScript answer:

# C (gcc), ~~60~~ 59 bytes

```
t;g(n,s){n=n?g(n,s+n--)+g(n,s):s%t<1;}f(n,k){t=k;n=g(n,0);}

```

Try it online!

*Saved a byte thanks to att!!!*
> 3 votes

# Answer
# Desmos, ~~74~~ 65 bytes

*-9 bytes thanks to Steffan*

```
f(n,k)=∑_{N=1}^{2^n}0^{mod(∑_{a=1}^namod(floor(2N/2^a),2),k)}

```

Try It On Desmos!

Try It On Desmos! - Prettified
> 3 votes

# Answer
# , 79 bytes

```
function(n,m)sum(!sapply(apply(expand.grid(rep(list(!1:0),n)),1,which),sum)%%m)
```

Attempt This Online!

`expand.grid` generates all permutations of `n` elements of `TRUE`/`FALSE`; then `which` identifies the `TRUE` index in each permutation: this is the powerset of `1:n`; get the `sum` of each (using `sapply`), find those that are zero modulo `m`, and `sum` the results.

Performing the `which` and `sum` calculations together costs more in R \< 4.1, since we need to declare a new `function`, but this is offset in more-recent R versions that can use `\` as a short form:

---

# ≥4.1, 72 bytes

```
\(n,m)sum(!apply(expand.grid(rep(list(!1:0),n)),1,\(x)sum(which(x)))%%m)
```

Attempt This Online!

---

I wrote all that, and then - before posting - browsed down to Arnauld's and att's answers, and realised that porting their beautiful recursive approach into R would be hugely shorter. Upvote them!

# ≥4.1, ~~49~~ 47 bytes

*Edit: -2 bytes thanks to a very nice golf by pajonk, using the indexing operator `[` as the recursive function name*

```
`[`=\(k,n,s=0)`if`(n,k[n-1,s]+k[n-1,s+n],!s%%k)
```

Attempt This Online!
> 3 votes

# Answer
# Wolfram Language (Mathematica), ~~53 41~~  38 bytes

~~-12~~ -15 bytes, thanks @att!

```
Tr[1##&@@@+++I^(4##&~Array~{##}/#)]/#&

```

Try it online!

Previous solution by @att

```
Sum[1##&@@+++I^(4k/#2Range@#),{k,#2}]/#2&

```

Try it online!

Previous solution by me:

```
f=PolynomialMod;f[Product[1+x^i,{i,1,#1}],x^#2-1]~f~x&

```

Try it online!

First I forgot the `&` and Mathematica simplified the entire expression to `QPochammer[-1,x,1+#1]/2`. At first I was quite happy: a way to shorten the code! Before I realized that it can't be right because this removes an entire argument of the function.
Sad times :(

Using 58 bytes we can get code that is much faster at evaluating the answer for large inputs, with the only issue that it gives the answer as an expression involving exponentials of complex expressions:

```
Tr[Product[1+E^(2i I π k/#2),{i,1,#}]~Table~{k,1,#2}]/#2&

```

The expressions are equivalent to the correct number, but Mathematica only simplifies it down if we add `FullSimplify@` in front, resulting in a total of 71 bytes.

Try it online!
> 3 votes

# Answer
# Jelly, 6 bytes

```
ŒP§%ċ0

```

Try it online!

## How?

```
ŒP§%ċ0  Full program: Dyadic link f(n, k):
ŒP      Powerset of n, which is implicitly converted to range [1..n]
  §     Sum of each
   %    Modulo each by k
    ċ0  Count the number of zeros

```

Edit: Whoops, Jonathan Allan beat me by one minute.
> 2 votes

# Answer
# Jelly, 6 bytes

```
ŒP§ọTL

```

A dyadic Link that accepts \\$n\\$ on the left and \\$k\\$ on the right and yields the count of subset sums of \\$\[1,n\]\\$ divisible by \\$k\\$.

**Try it online!**

### How?

```
ŒP§ọTL - Link: n, k
ŒP     - powerset of [1,n]
  §    - sums
   ọ   - how many times is each divisible by k?
    T  - truthy indices
     L - length

```

---

Alternatively, using filter-keep: `ŒP§ọƇL`
> 2 votes

# Answer
# Charcoal, 20 bytes

```
Ｉ№﹪ＥＸ²Ｎ↨Ｅ⮌↨ι²∧λ⊕μ¹Ｎ⁰

```

Try it online! Link is to verbose version of code. Explanation:

```
     ²                  Literal integer `2`
    Ｘ                   Raised to power
      Ｎ                 First input as an integer
   Ｅ                    Map over implicit range
           ι            Current value
          ↨             Converted to base
            ²           Literal integer `2`
         ⮌              Reversed
        Ｅ               Map over bits
              λ         Current bit
             ∧          Logical And
                μ       Current index
               ⊕        Incremented
       ↨         ¹      Take the sum
  ﹪                     Vectorised modulo
                  Ｎ     Second input as an integer
 №                 ⁰    Count the zeros
Ｉ                       Cast to string
                        Implicitly print

```

Base `1` conversion is used to sum as the first subset is empty and `Sum` doesn't like that.

For 23 bytes, a much more efficient version:

```
≔ＥＮ¬ιθＦＮＵＭθ⁺κ§θ⁻λ⊕ιＩ§θ⁰

```

Try it online! Link is to verbose version of code. Takes arguments in the order `k, n`. Explanation:

```
≔ＥＮ¬ιθ

```

Make a list of `k` elements where the first is `1` and the rest are `0`.

```
ＦＮ

```

For `i` from `1..n` (actually 0-indexed but I use `Incremented(i)` below)...

```
ＵＭθ⁺κ§θ⁻λ⊕ι

```

... cyclically rotate the list by `i` and vectorised add it back.

```
Ｉ§θ⁰

```

Output the first element of the result.
> 2 votes

# Answer
# 05AB1E, 6 bytes

```
LæOsÖO

```

Try it online!
> 2 votes

# Answer
# Factor \+ `math.combinatorics math.unicode`, 50 bytes

```
[ [1,b] all-subsets swap '[ Σ _ mod 0 = ] count ]

```

Try it online!

Takes input as `k n`.
> 2 votes

# Answer
# Burlesque, 17 bytes

```
roR@{++dv}x/1iafl

```

Try it online!

```
ro     # Range 1..n
R@     # All subsets
{
 ++    # Sum
 dv    # Divides (a%b == 0)
}
x/     # reorder stack
1ia    # Insert divisor in position 1 (zero-indexed)
fl     # Count of matches

```
> 2 votes

# Answer
# Husk, 7 bytes

```
#¦⁰mΣṖḣ

```

Try it online!

```
#¦⁰mΣṖḣ
      ḣ  # get the sequence 1..arg2
     Ṗ   # and get the powerset (all finite subsets);
   m     # now map over each subset:
    Σ    # get the sum
#        # and count the number of results
 ¦       # that are divisible by
  ⁰      # arg1

```
> 1 votes

---
Tags: code-golf, math, combinatorics, set-partitions
---


title: Prime Power Switch

text:
# Question
Title: Prime Power Switch
**Input:** A positive integer `n=p^q` where `p` and `q` are prime.

**Output:** Output the result of `q^p`

**Test cases (in, out):**

```
4, 4
8, 9
25, 32
27, 27
49, 128
121, 2048
125, 243
343, 2187
1331, 177147
3125, 3125,
16807, 78125,
823543, 823543
161051, 48828125
19487171, 1977326743

```

**Scoring:**
This is , so may the shortest code in bytes win! Input and output maybe in any reasonable format suitable to your language.

Related:
Recover the power from the prime power
Recover the prime from the prime power

# Answer
# 05AB1E, 5 bytes

```
ÓOsfm

```

Try it online!

**Commented:**

```
        # implicit input            25
Ó       # prime factor exponents    [0, 0, 2]
 O      # sum                       2
  s     # swap (with input)         25, 2
   f    # unique prime factors      [5], 2
    m   # power                     [32]

```
> 4 votes

# Answer
# Python 2, 56 bytes

```
n=input()
p=2
while n%p:p+=1
P=p**n-1
print(n**n/P%P)**p

```

Try it online!

We first find the prime \\$p\\$ for which \\$n=p^q\\$ by incrementing \\$p\\$ until we get a divisor on \\$n\\$. After that, we find the exponent \\$q\\$ with a mathematical trick first discovered by Sp3000 and used in Perfect power logarithms on Anarchy Golf.

We note that $$ \frac{n-1}{p-1} = \frac{p^q-1}{p-1} = 1 + p + p^2 \dots+p^{q-2}+p^{q-1}$$ Working modulo \\$p-1\\$, we have \\$p \equiv 1\\$, so each of \\$q\\$ the summands on the right hand side equals 1, and so: $$ \frac{n-1}{p-1} \equiv q \space \bmod (p-1)$$

We'd now like to extract \\$q\\$. We'd like to get there by applying the modulus operator `%(p-1)` to the left hand side. But this requires that \\$q\<p-1\\$, which is not guaranteed, or we'll get a different value of `q%(p-1)`.

Fortunately, we can get around this with one more trick. We can replace \\$n\\$ with \\$n^c\\$ and \\$p\\$ with \\$p^c\\$ for some positive number \\$c\\$, and still have \\$n^c=(p^c)^q\\$. Since the exponent \\$q\\$ relating them is unchanged, we can extract it as above, but make it so that \\$q\
 15 votes

# Answer
# Bash \+ Linux utils, 17

```
factor|dc -e?zr^p

```
* `factor` takes a number as input and factorizes it. The output is the input number, followed by a colon, followed by a spaced-separated list of all the prime factors.
* This list is piped to `dc` which evaluates the following `e`xpression:
    + `?` reads the whole line as input. dc cannot parse the input number followed by the colon, so it ignores it. Then it parses all the space-separated prime factors and pushes them to the stack.
    + `z` takes the number of items on the stack (number of prime factors) and pushes that to the stack
    + `r` reverses the top two items on the stack
    + `^` exponentiates, giving the required answer
    + `p` prints it.

Try it online!
> 6 votes

# Answer
# MATL, ~~8~~ 5 bytes

-3 bytes thanks to @LuisMendo

```
&YFw^

```

Try it online!
> 5 votes

# Answer
# , 9 8 bytes

```
2^~/@p:]

```

Try it online!

* `2 p: ]` returns a list of primes and their exponents.
* `^~/@` then swap the arguments and exponentiate
> 4 votes

# Answer
# Python 2, 62 bytes

```
n=input()
p=2
q=-1
while n%p:p+=1
while n:n/=p;q+=1
print q**p

```

Try it online!
> 4 votes

# Answer
# C (gcc) `-lm`, 47 bytes

```
p;f(n){for(p=1;n%++p;);p=pow(log(n)/log(p),p);}

```

Try it online!
> 4 votes

# Answer
# Brachylog, 6 bytes

```
ḋ⟨l^h⟩

```

Try it online! On the prime decomposition  (like `[5, 5]`), length `l` `^` first element `h`.

A nicer and more Brachylog-y solution, that is one byte longer:

```
 ~^ṗᵐ↔≜^

```

Try it online! Reverse `~^` to get two Numbers `[A,B]` so that `Input = A^B`, while both are prime `ṗᵐ`. Flip  the list to `[B,A]`, actually find the numbers  and output `B^A`.
> 4 votes

# Answer
# Japt, 6 bytes

```
k
ÊpUg

```

Try it

```
k\nÊpUg     :Implicit input of integer U
k           :Prime factors
 \n         :Reassign to U
   Ê        :Length
    p       :Raised to the power of
     Ug     :First element of U

```
> 3 votes

# Answer
# JavaScript (ES7),  ~~47 46~~  44 bytes

Uses a recursive function that first looks for the smallest divisor \\$k\ge2\\$ of \\$n\\$ and then counts how many times \\$n\\$ can be divided by \\$k\\$. The result is raised to the power of \\$k\\$.

```
n=>(k=2,g=_=>n%k?n>1&&g(k++):1+g(n/=k))()**k

```

Try it online!

### Commented

```
n => (          // main function taking n
  k = 2,        // start with k = 2
  g = _ =>      // g is a recursive function ignoring its input
    n % k ?     //   if k is not a divisor of n:
                //     this point of the code is reached during the first step
                //     of the algorithm; but it's also reached on the last
                //     iteration when n = 1, which is why ...
      n > 1 &&  //     ... we test whether n is greater than 1 ...
        g(k++)  //       ... in which case we do a recursive call with k + 1
    :           // else (k has been found):
      1 +       //   add 1 to the final result
      g(n /= k) //   and do a recursive call with n / k
)()             // initial call to g
** k            // raise the result to the power of k

```
> 3 votes

# Answer
# ~~36~~ ~~28~~ ~~1~~ 36 bytes

Using the fact that exactly `p` powers of `n` are factors of `n^p`:

```
sum(a<-!max(b<-2:scan())%%b)^b[a][1]

```

Try it online!

but using a function definition does better (by moving `function(m)` to the header part!)

```
f=function(m)
sum(a<-!m%%(b<-2:m))^b[a][1]

```

Try it online!

with the ultimate improvement in length (1 byte!) produced by defining everything as the function argument (in the header of Try It Online).

```
f=function(m,b=2:m,a=!m%%b,d=sum(a)^b[a][1]) d

```

but this is not keeping with the code golf spirit!
> 3 votes

# Answer
# Haskell, ~~42~~, 39 bytes

```
f x|r<-[2..x]=[z^w|z<-r,w<-r,w^z==x]!!0

```

Try it online!

* 3 bytes saved by @xnor
> 3 votes

# Answer
# , 37 bytes

```
log(n<-scan(),p<-(b=2:n)[!n%%b][1])^p

```

Try it online!

My best effort, sadly 1-byte longer than the Xi'an's much-cleverer R answer, but posting anyway in the competitive spirit.

Uses the straightforward approach of finding the prime factor (`p<-(b=2:n)[!n%%b][1]`), then the exponent (`log(n,p)`) and finally raising the exponent to the power of the factor (`log(n,p)^p`).
> 3 votes

# Answer
# Ruby, 56 bytes

```
n=gets.to_i
p=2
p+=1while n%p>0
w=p**n-1
p (n**n/w%w)**p

```

Port of xnor's Python 3 answer.

Try it online! (headers and footers courtesy of ovs. :D)
> 3 votes

# Answer
# Vyxal, 5 bytes

```
ǐ₌Lhe

```

Try it Online!

## How?

```
ǐ₌Lhe
ǐ     # Prime factors with duplicates
 ₌    # Apply both of next two elements and push both results to the stack:
  L   #  Length
   h  #  First item
    e # Exponentiate these two (length ^ first item)

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), 24 bytes

```
#2^#&@@@FactorInteger@#&

```

Try it online!

Returns `{q^p}`, a singleton list.

```
        FactorInteger@# (* {{p,q}} *)
#2^#&@@@                (* { q^p } *)

```
> 2 votes

# Answer
# Retina, 59 bytes

```
.+
*
~`(?=(__+?)\1*$)((?=(_+)(\3+)$)\4)+
_+¶$$.($.1*$($#2$*

```

Try it online! Link includes faster test cases. Explanation:

```
.+
*

```

Convert the input to unary.

```
(?=(__+?)\1*$)((?=(_+)(\3+)$)\4)+

```

First, find the smallest nontrivial factor, which will necessarily be `p`. Secondly, count the number of times `q` that `n` can be replaced with its largest proper factor. (The proper factor will be `n/p` on the first pass and eventually decrease to `1` which is left unmatched but this doesn't affect the result.)

```
_+¶$$.($.1*$($#2$*

```

Generate a Retina stage which takes `n` as input and calculates (in decimal) the result of multiplying `1` by `q` `p` times, thus calculating `q^p`.

```
~`

```

Evaluate the resulting code, thus calculating the desired result.
> 2 votes

# Answer
# Scala, 63 bytes

```
n=>2 to n find(n%_<1)map{p=>import math._;pow(log(n)/log(p),p)}

```

Try it online!

Finds the first factor of `n`, which must be `p` because `n` is a prime power, then finds \\$\log\_p(n)^p\\$. Returns an `Option[Double]` that's a `Some[Double]` if the input is valid.
> 2 votes

# Answer
# Jelly, 6 bytes

```
ÆFẎṪ*$

```

Try it online!

# Jelly, 6 bytes

```
ÆFẎ*@Ɲ

```

Try it online!

# Jelly, 6 bytes

```
ÆfL*ḢƊ

```

Try it online!

A 5-byter feels possible...
> 2 votes

# Answer
# , 8 bytes

```
2^~/@p:]

```

Try it online!

J has a built-in that gives the prime factorization of a given integer in prime-exponent form. Then it's just a matter of applying exponentiation in reverse (`^~`) between the two numbers.

(Happens to be the same as Jonah's answer; somehow didn't notice before I submitted the answer...)

---

Because it is also solvable using `f&.g` ("Under"; do action g, do action f, then undo action g), here are some interesting ones:

### 10 bytes

```
|.&.(2&p:)
     2&p:  Prime factorization into prime-exponent form
|.         Swap the prime and exponent
  &.       Undo `2&p:`; evaluate the "prime" raised to "exponent"

```

Try it online!

### 10 bytes

```
({.##)&.q:
        q:  Prime factorization into plain list of primes
 {.         Head (prime)
   #        Copies of
    #       Length (exponent)
 {.##       Essentially swap the role of prime and exponent
      &.    Undo `q:`; product of all "primes"

```

Try it online!
> 2 votes

# Answer
# Alice, 13 bytes

```
/ \f~#oE/
 i@

```

Try it online!

**Explanation:**

```
/           Switch to Ordinal mode
 i          Push the input as a string
  \         Switch to Cardinal mode
   f        Pop n, implicitly convert n to an integer,
            and push the prime factors of n as pairs of prime and exponent
    ~       Swap the top two elements of the stack
     #      Skip the next command
       E    Pop y, pop x. If y is non-negative, push x ^ y
        /   Switch to Ordinal mode
      o     Pop s, then output s as a string.
    ~       Swap the top two elements of the stack.
  \         Switch to Cardinal mode
  @         Terminate the program

```
> 2 votes

# Answer
# Forth (gforth), 85 bytes

```
: f dup 2 do dup i mod 0= if i leave then loop tuck swap s>f fln s>f fln f/ s>f f** ;

```

Try it online!

Works like Noodle9's C answer. Takes an integer and returns a floating-point number on the FP stack.

### How it works

```
: f ( n -- float )
  dup 2 do           \ loop from i = 2..n-1
    dup i mod 0= if  \ if n % i == 0
      i leave        \ ( n p ) we found p; leave the loop
    then             \ end if
  loop               \ end loop
  tuck swap          \ ( p p n )
  s>f fln s>f fln    \ ( p F:ln(n) F:ln(p) )
  f/                 \ ( p F:q ) q = ln(n)/ln(p)
  s>f f**            \ ( F:q**p )
;

```
> 2 votes

# Answer
# Pyth, ~~7~~ 6 bytes

-1 byte thanks to @FryAmTheEggman

```
^lPQhP

```

Try it online!

## Explanation

```
^lPQhP
 l      # length of
  PQ    # prime factors of input
^       # raised to power of
    hP  # first element in prime factors of input

```
> 1 votes

# Answer
# Io, ~~57~~ 55 bytes

Fixed a bug kindly pointed out by @DominicvanEssen

```
method(i,p :=2;while(i%p>0,p=p+1);i log(p)floor pow(p))

```

Try it online!
> 1 votes

# Answer
**APL (NARS2000 0.5.14), 9 characters 8 characters (thanks to gurus in APL Orchard):**

```
(⍴*1∘↑)π

```

**How it works:**

Take input 8 as example. `π` breaks down 8 into vector of prime factors `2 2 2`. The fork `⍴*1∘↑` takes one element from `2 2 2` as exponent, applies this to length of vector `2 2 2` which is `3`, giving `3^2 = 9`.
> 1 votes

# Answer
# Factor \+ `math.primes.factors`, 34 bytes

```
[ factors dup length swap last ^ ]

```

Try it online!
> 1 votes

# Answer
# Desmos, ~~61~~ 10+38=48 bytes

```
l=log_m(n)
\sum_{m=2}^{n-1}(sign(l-ceil(l))+1)l^m

```

View it online (note that large values may fail because Desmos doesn't handle large numbers well)

I decided to revisit this because I felt like outgolfing myself, and I remember this having potential inefficiencies. I could only find one improvement, but it seemed substantial enough for the edit.

Input is via the variable `n`, output via the second calculation. If taking input via a variable feels wrong, feel free to add two bytes for a `n=`.

Not horribly efficiently golfed. About 70% of the code is just dedicated to finding one factor, and there's surely a more efficient way to factor numbers in Desmos, but I haven't found one yet, and Desmos is lacking in built-ins relating to factorization or prime numbers.

Instead, we simply observe that since \\$p\\$ and \\$q\\$ are prime, then \\$p\*p...\*p\\$ must be the only factorization of \\$n\\$ which can be represented with integer values, because the list of \\$p\\$s cannot be split into any other even groups. Therefore, we can just interate through all integers \\$m \in 2,3,...,n-1\\$ and find the value satisfying \\$log\_mn \in \mathbb{Z}\\$ (the set of integers). We do this in the code using `sign(log_m(n)-ceil(log_m(n)))+1`, which gives us a nice 1 when integeral and 0 when not. We multiply by `log_m(n)^m` to give us our new value, and add up the results for all values 2 through n-1 to single out the answer.
> 0 votes

# Answer
# Husk, 5 bytes

```
§^←Lp

```

Try it online!
> 0 votes

---
Tags: code-golf, primes
---


title: In between fractions

text:
# Question
Title: In between fractions
Given two positive integer fractions \\$x\\$ and \\$y\\$ such that \\$x \< y\\$, give the fraction \\$z\\$ with the smallest positive integer denominator such that it is between \\$x\\$ and \\$y\\$.

For example \\$x=2/5\\$, \\$y=4/5\\$, the answer is \\$1/2\\$. Other fractions such as \\$3/5\\$ are also in between the two, but \\$1/2\\$ has a denominator of \\$2\\$ which is smaller.

As input you will receive 4 positive integers, the numerators and the denominators of \\$x\\$ and \\$y\\$, you may assume these fractions are fully reduced. You should output the numerator and the denominator of \\$z\\$.

If there are multiple valid numerators, you may output any or all of them.

This is so the goal is to minimize the size of your source code as measured in bytes.

### Test cases

```
2/5 4/5 -> 1/2
1/1 2/1 -> 3/2
3/5 1/1 -> 2/3
5/13 7/18 -> 12/31
12/31 7/18 -> 19/49

```

Sample implementation in Haskell

# Answer
# Husk, ~~20~~ ~~12~~ 11 bytes

```
ḟ<⁰MS/ȯ→⌊*N

```

Try it online!

Generates an infinite list of fractions by going through each integer `N` as denominator in turn and constructing the numerator `floor(N*x)+1`.
Then searches for the first one that is `<y`.

```
ḟ<⁰MS/ȯ→⌊*N
   M      N  # map over all integers starting at 1:
         *   # multiply it by (implicit input) x
        ⌊    # get the floor
       →     # and increment it,
    S/ȯ      # and now divide all of that by itself;
ḟ            # finally, get the first result that
 <⁰          # is less than y

```
> 7 votes

# Answer
# PARI/GP, 36 bytes

```
f(a,b,d)=until(b*d++>n=a*d\1+1,);n/d

```

Attempt This Online!

Takes two fractions and outputs a fraction.

For inputs \\$a,b\\$, let \\$d\\$ loops over all positive integers until \\$b\ d\>\lfloor a\ d\rfloor+1\\$, and returns \\$(\lfloor a\ d\rfloor+1)/d\\$.
> 5 votes

# Answer
# Python 2, 61 bytes

```
a,p,b,q=input();r=c=0
while r*b<=q*c:r+=1;c=r*a/p+1
print c,r
```

Attempt This Online!

Rather naïve.

---

# Python with `fractions`, 57 bytes

```
def f(x,y,d=0):
 while(n:=x*d//1+1)>=y*d:d+=1
 return n,d
```

Attempt This Online!

Port of alephalpha's PARI/GP answer.
> 4 votes

# Answer
# Vyxal, 17 bytes

```
ƒ/Þ∞*⌊›Þ∞/'⁰ƒ/<;h

```

Try it Online!

Port of Husk answer.
> 3 votes

# Answer
# C (clang), <sup>~~67~~</sup> 62 bytes

```
n;d;f(*i,*j,k,l){for(d=n=0;*i*d<=*j*n;)n=++d*k/l+1;*i=n;*j=d;}

```

Try it online!

Inputs the two fractions as \\$2\\$ pointers to integers for the numerator and denominator of the second fraction. And then \\$2\\$ integers as the numerator and denominator of the first fraction.
Returns the in between fraction through the two pointers.
> 2 votes

# Answer
# Wolfram Language (Mathematica), 36 bytes

```
n&@For[d=1,(n=⌊d#+1⌋/d++)>=#2,]&

```

Try it online!

Port of alephalpha's PARI/GP solution.
> 2 votes

# Answer
# Charcoal, 35 bytes

```
ＮθＮηＮζＮεＩ§ΦＥ⊕⁺ηε⟦⊕÷×θκηκ⟧›×ζκ×§ι⁰ε⁰

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｎθ                                  Numerator of `x` as an integer
  Ｎη                                Denominator of `x` as an integer
    Ｎζ                              Numerator of `y` as an integer
      Ｎε                            Denominator of `y` as an integer
              η                     Denominator of `x`
             ⁺                      Plus
               ε                    Denominator of `y`
            ⊕                       Incremented
           Ｅ                        Map over implicit range
                    θ               Numerator of `x`
                   ×                Multiplied by
                     κ              Current index
                  ÷                 Integer divided by
                      η             Denominator of `x`
                 ⊕                  Incremented
                       κ            Current index
                ⟦       ⟧           Make into list
          Φ                         Filtered where
                           ζ        Numerator of `y`
                          ×         Multiplied by
                            κ       Current index
                         ›          Is greater than
                              § ⁰   First index of
                               ι    Current list
                             ×      Multiplied by
                                 ε  Denominator of `y`
         §                        ⁰ First element
        Ｉ                           Cast to string
                                    Implicitly print

```

The sum of the denominators is a sufficient limit since \\$ \frac a b \< \frac { a + b } { c + d } \< \frac c d \\$ if \\$ \frac a b \< \frac c d \\$.
> 1 votes

# Answer
# JavaScript (ES6), 50 bytes

Expects \\$p/q\\$ and \\$P/Q\\$ as `(p,q,P)(Q)` and returns \\$m/n\\$ as `[m,n]`.

Based on alephalpha's method.

```
(p,q,P,n=0)=>g=Q=>++n*P>(m=-~(n*p/q))*Q?[m,n]:g(Q)

```

Try it online!
> 1 votes

# Answer
# TI-Basic, 30 bytes

```
Prompt A,B
Repeat BAns>1+int(AAns
Ans+1
End
1/Ans(1+int(AAns

```

Port of alealpha's answer. Takes input as 2 fractions and output a fraction. The `/` symbol represents the fraction slash.
> 1 votes

# Answer
# 05AB1E, 24 bytes

```
∞ε¹.E*ï>y‚D¿÷'/ý}.Δ‚.E`›

```

Port of *@DominicVanEssen*'s Husk answer, but without implicit fraction support.

Try it online or verify all test cases.

**Explanation:**

```
∞           # Push an infinite positive list: [1,2,3,...]
 ε          # Map over each value:
  ¹         #  Push the first input
   .E       #  Evaluate it as Elixir
     *      #  Multiply it to the current value
      ï     #  Floor it
       >    #  Increase it by 1
  y‚        #  Pair it with the current value
    D       #  Duplicate this pair
     ¿      #  Pop and push the gcd (greatest common divisor)
      ÷     #  Integer-divide the pair by this gcd
       '/ý '#  Join the pair with "/"-delimiter to a string
 }.Δ        # After the map: find the first value which is truthy for:
    ‚       #  Pair it with the (implicit) second input
     .E     #  Evaluate both strings as Elixir
       `    #  Pop and push both values to the stack
        ›   #  Check that the first is larger than the second
            # (after which the found fraction-string is output implicitly)

```
> 0 votes

# Answer
# Japt, 24 bytes

Settled with a port of Arnauld's solution for now.

```
T=°Y*U/VW*Y§X*ÒT?ß:[ÒTY]

```

Try it
> 0 votes

# Answer
# x86\_64 assembly, 48 bytes

This routine expects arguments `eax/ebx, ecx/edx` and returns the result in `r9/r11` (and registers `r8` and `r10` are clobbered).

```
    .text
    .globl f
f:
    xor %r8, %r8
    xor %r9, %r9
    xor %r10, %r10
    inc %r8
    mov %r8, %r11
    .Lloop:
    cmp %rdx, %rcx
    ja  .L1
# a/b < c/d <= 1: return 1 / f(d/c,b/a)
    xchg    %rax, %rdx
    xchg    %rbx, %rcx
# 1/ matrix to multiply on right is [0 1; 1 0]
    xchg    %r8, %r9
    xchg    %r10, %r11
    jmp .Lloop
    .L1:
# 1+ matrix to multiply on right is [1 1; 0 1]
    add %r8, %r9
    add %r10, %r11
# 1 <= a/b < c/d: return 1 + f(a/b-1, c/d-1)
    sub %rdx, %rcx
    sub %rbx, %rax
    jae .Lloop
# a/b < 1 < c/d:
# return 0/1 (which becomes a return of 1/1 with the 1+ matrix
# merged between this case and the previous one)
    ret

```

C test driver (requires GCC):

```
#include <stdio.h>

void f_wrap(unsigned long a,
           unsigned long b,
           unsigned long c,
           unsigned long d,
           unsigned long *e,
           unsigned long *f) {
  register unsigned long r9 __asm__("r9");
  register unsigned long r11 __asm__("r11");
  __asm__("call f" :
      "=a"(a), "=b"(b), "=c"(c), "=d"(d), "=r"(r9), "=r"(r11) :
      "0"(a), "1"(b), "2"(c), "3"(d) :
      "r8", "r10");
  *e = r9;
  *f = r11;
}

void test_f(unsigned long a,
        unsigned long b,
        unsigned long c,
        unsigned long d) {
  unsigned long e;
  unsigned long f;
  f_wrap(a, b, c, d, &e, &f);
  printf("%lu/%lu %lu/%lu -> %lu/%lu\n", a, b, c, d, e, f);
}

int main() {
  test_f(2, 5, 4, 5);
  test_f(1, 1, 2, 1);
  test_f(3, 5, 1, 1);
  test_f(5, 13, 7, 18);
  test_f(12, 31, 7, 18);
  test_f(2, 5, 1, 2);
  test_f(3, 7, 1, 2);
  // 3.14 = 314/100 = 157/50; 3.15 = 315/100 = 63/20
  test_f(157, 50, 63, 20);
  // 3.1415 = 31415/10000 = 6283/2000; 3.1416 = 31416/10000 = 3927/1250
  test_f(6283, 2000, 3927, 1250);
  return 0;
}

```

And disassembly of the code as it ended up in the executable:

```
0000000000001229 <f>:
    1229:       4d 31 c0                xor    %r8,%r8
    122c:       4d 31 c9                xor    %r9,%r9
    122f:       4d 31 d2                xor    %r10,%r10
    1232:       49 ff c0                inc    %r8
    1235:       4d 89 c3                mov    %r8,%r11
    1238:       48 39 d1                cmp    %rdx,%rcx
    123b:       77 0d                   ja     124a <f+0x21>
    123d:       48 92                   xchg   %rax,%rdx
    123f:       48 87 d9                xchg   %rbx,%rcx
    1242:       4d 87 c1                xchg   %r8,%r9
    1245:       4d 87 d3                xchg   %r10,%r11
    1248:       eb ee                   jmp    1238 <f+0xf>
    124a:       4d 01 c1                add    %r8,%r9
    124d:       4d 01 d3                add    %r10,%r11
    1250:       48 29 d1                sub    %rdx,%rcx
    1253:       48 29 d8                sub    %rbx,%rax
    1256:       73 e0                   jae    1238 <f+0xf>
    1258:       c3                      ret

```

---

The basic idea in pseudocode behind this implementation is inspired by continued fractions:

```
f(x,y):
    if y <= 1
        return 1 / f(1/y, 1/x)
    else if x >= 1
        return 1 + f(x-1, y-1)
    else
        return 1/1

```

(Do note, however, that in certain cases, this makes a recursive call to `f` with `y = 1 / 0` where we treat that as infinity.)

Now, the biggest optimization I made was to note that at any point, the transformations on the stack to the return value form a projective linear transformation. So, in the assembly version, instead of maintaining a call stack, I maintain a 2x2 matrix representing the required projective linear transformation so far in registers `[r8 r9; r10 r11]`.

Aside from that, and some usual optimizations, there was a folding of common code between the second and third cases: both involve taking the sum of the two columns of the transformation matrix.

(However, I didn't make any effort to try different register allocations, and see if others might end up saving a couple bytes.)
> 0 votes

---
Tags: code-golf, math, number-theory, rational-numbers
---