25
\$\begingroup\$

Today, as I'm writing this, is March 31st. In the US, this is 3/31. I was playing around with 331 as a number to come up with a challenge, and found that its residues (modulo small numbers) is palindromic. 331%2=1, 331%3=1, 331%4=3, 331%5=1, 331%6=1 (11311).

Your challenge here is, when given an integer n > 2, output the first n positive numbers that have palindromic residue when taken modulo [2,n].

For example, for input 7, the output should be 1, 42, 43, 140, 182, 420, 421. Here's the chart explaining why that's the case:

        mod
num | 2 3 4 5 6 7
-----------------
  1 | 1 1 1 1 1 1
 42 | 0 0 2 2 0 0
 43 | 1 1 3 3 1 1
140 | 0 2 0 0 2 0
182 | 0 2 2 2 2 0
420 | 0 0 0 0 0 0
421 | 1 1 1 1 1 1

Input

A single positive integer n with n > 2 in any convenient format.

Output

The resulting array/list of the first n palindromic residues, as outlined above. Again, in any suitable format.

Rules

  • For n > 10, assume the residue list to be flattened before checking whether it's a palindrome. That is, [1, 10, 11] is palindromic, but [1, 10, 1] is not.
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • If possible, please include a link to an online testing environment so other people can try out your code!
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

Examples

[input]
[output]

3
[1, 6, 7]

4
[1, 4, 5, 8]

5
[1, 50, 60, 61, 110]

6
[1, 30, 31, 60, 61, 90]

7
[1, 42, 43, 140, 182, 420, 421]

8
[1, 168, 169, 336, 337, 504, 505, 672]

9
[1, 2520, 2521, 5040, 5041, 7560, 7561, 10080, 10081]

10
[1, 280, 281, 560, 1611, 1890, 1891, 2170, 2171, 2241]

11
[1, 22682, 27720, 27721, 50402, 55440, 55441, 78122, 83160, 83161, 105842]
\$\endgroup\$
  • \$\begingroup\$ Is the output supposed to be ordered? \$\endgroup\$ – Arnauld Mar 31 '17 at 15:24
  • \$\begingroup\$ @Arnauld It doesn't need to be, no, provided that it includes only the first n elements. \$\endgroup\$ – AdmBorkBork Mar 31 '17 at 15:27
  • 2
    \$\begingroup\$ arrgh ... your challenge = your rules, but "[1, 10, 11] is palindromic, but [1, 10, 1] is not" seems so mathematically wrong. \$\endgroup\$ – Greg Martin Mar 31 '17 at 16:25
  • 1
    \$\begingroup\$ @GregMartin Stringy palindromes, not mathy palindromes. ;-) \$\endgroup\$ – AdmBorkBork Mar 31 '17 at 16:34
  • 1
    \$\begingroup\$ grr. The whole stringy instead of mathy palindrome makes this a thousand times harder in certain languages. Oh well. \$\endgroup\$ – MildlyMilquetoast Mar 31 '17 at 17:06

12 Answers 12

9
\$\begingroup\$

Haskell, 57 bytes

f n=take n[x|x<-[1..],(==)=<<reverse$show.mod x=<<[2..n]]

Usage example: f 4 -> [1,4,5,8]. Try it online!

The first =<< is in function context and translates to the lambda \x -> reverse x == x and the second =<< is in list context and equivalent to concatMap, i.e. map-and-flatten-one-list-level.

\$\endgroup\$
5
\$\begingroup\$

05AB1E, 12 bytes

µN2¹Ÿ%JÂQD½–

Try it online!

Explanation

µ              # until counter equals input do:
 N             # push current iterations number
     %         # modulus each in
  2¹Ÿ          # range [2 ... input]
      J        # joined to string
       ÂQ      # equals it's reverse
         D     # duplicate
          ½    # if true, increase counter
           –   # if true print iteration number
\$\endgroup\$
  • \$\begingroup\$ Do you post 05AB1E answers from your phone? Cause you do these quick lol. \$\endgroup\$ – Magic Octopus Urn Mar 31 '17 at 17:47
  • \$\begingroup\$ @carusocomputing: Very seldom as a lot of the characters in cp-1252 are annoying to type/copy-paste on the phone. This one popped up right before I checked my computer after dinner, so I had pretty good timing :) \$\endgroup\$ – Emigna Mar 31 '17 at 18:27
4
\$\begingroup\$

Mathematica, 79 bytes

NestList[#+1//.x_/;!PalindromeQ[ToString/@Mod[x,Range@n+1]<>""]:>x+1&,1,n=#-1]&
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 104 bytes

f=(n,x=(k=--n,2))=>k?([...Array(n)].map(_=>(r=x%++i+r,x%i),i=1,r='').join``==r?k--&&x+' ':'')+f(n,x+1):1

Demo

NB: Because of the numerous recursive calls, this will crash for n > 8 on Firefox or n > 10 on Chrome.

f=(n,x=(k=--n,2))=>k?([...Array(n)].map(_=>(r=x%++i+r,x%i),i=1,r='').join``==r?k--&&x+' ':'')+f(n,x+1):1

for(n = 2; n < 9; n++) {
  console.log(n, '=>', f(n));
}

\$\endgroup\$
4
\$\begingroup\$

Python 2, 98 97 bytes

n=input();i=j=0
while i<n:
 j+=1;l=''
 for k in range(2,n+1):l+=`j%k`
 if l==l[::-1]:i+=1;print j

Try it Online!

\$\endgroup\$
  • \$\begingroup\$ you can drop the entire string conversion \$\endgroup\$ – Rod Mar 31 '17 at 16:10
  • \$\begingroup\$ @Rod Thanks, but I believe that would fail on input 12 due to the strange rule that [1, 10, 11] is considered a palindrome \$\endgroup\$ – math junkie Mar 31 '17 at 16:46
3
\$\begingroup\$

MATL, 19 bytes

Thanks to @AdmBorkBork for pointing out a mistake in an earlier version of the code, now corrected

`@Gq:Q\VXztP=?@]NG<

Try it online!

Explanation

`        % Do...while
  @      %   Push iteration index, starting at 1
  Gq:Q   %   Push [2 3 ... n], where n is the input
  \      %   Modulo, element-wise
  V      %   Convert to string. Numbers are separated by spaces
  Xz     %   Remove spaces
  tP     %   Duplicate, flip
  =      %   Equal? (element-wise)
  ?      %   If all results were true
    @    %     Push current iteration index. It is one of the sought numbers
  ]      %   End
  N      %   Push number of elements in stack
  G      %   Push input n
  <      %   Less than? This is the loop condition
         % End (implicit). Display (implicit)
\$\endgroup\$
3
\$\begingroup\$

Scala, 90 86 82 bytes

(n:Int)=>Stream.from(1)filter{i=>val d=(2 to n)map(i%)mkString;d.reverse==d}take(n)

Explanation

Stream.from(1)                              // From an infinite Stream starting from 1,
    filter ( i => {                         // keep only elements matching the next condition :
        val d=(2 to n)map(i%)mkString;      // Generate residues and convert to String,
        d.reverse==d                        // return true if palindrom, false otherwise
    })take(n)                               // Finally, take the n first elements matching the condition

Test cases

val f = (n:Int)=>...    // assign function
(3 to 11).foreach { i =>
    println(i + "\n" + f(i).mkString(", ") + "\n")
}

Results

3
1, 6, 7

4
1, 4, 5, 8

5
1, 50, 60, 61, 110

6
1, 30, 31, 60, 61, 90

7
1, 42, 43, 140, 182, 420, 421

8
1, 168, 169, 336, 337, 504, 505, 672

9
1, 2520, 2521, 5040, 5041, 7560, 7561, 10080, 10081

10
1, 280, 281, 560, 1611, 1890, 1891, 2170, 2171, 2241

11
1, 22682, 27720, 27721, 50402, 55440, 55441, 78122, 83160, 83161, 105842

Edits

#1 (90 => 86)

  • anonymous function

#2 (86 => 82)

  • remove useless dot characters after parenthesis or bracket (ex. : (2 to n).map(%i) => (2 to n)map(%i)
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Martin Ender Apr 2 '17 at 13:23
  • \$\begingroup\$ Thanks! I was wondering if I could change def f(n:Int)= to (n:Int)=>, since it also defines a function (but without name). It saves 4 bytes ! \$\endgroup\$ – norbjd Apr 3 '17 at 9:13
  • \$\begingroup\$ Yes, unnamed functions are allowed, provided you don't need the name for a recursive call or something like that. \$\endgroup\$ – Martin Ender Apr 3 '17 at 9:15
  • \$\begingroup\$ Great, edited :) \$\endgroup\$ – norbjd Apr 3 '17 at 9:32
2
\$\begingroup\$

Jelly, 12 bytes

%ЀḊDFŒḂ
1ç#

How?

1ç# - Main link: n
1   - initialise "i" at 1
  # - increment i and yield a list of the first n truthful results of:
 ç  -     last link (1) as a dyad

%ЀḊDFŒḂ - Link 1, test a value "i" for mod [2,n] being palindromic: i, n
 Ѐ      - for each, mapped over the right argument, i.e. for j = 1 to n:
%        -     i modulo j
   Ḋ     - dequeue, i.e. discard the modulo 1 result
    D    - convert to decimal list (vectorises)
     F   - flatten into one list
      ŒḂ - is palindromic?

Try it online!

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

CJam, 28 bytes

0ri:N{{)_N),2>f%s_W%#}g_p}*;

Try it online!

Explanation

0          e# Push 0, the value we'll repeatedly increment to search for valid outputs.
ri:N       e# Read input, convert to integer, store in N.
{          e# Run this block N times...
  {        e#   Run this block until the condition is true, which will find the next
           e#   number with palindromic residues...
    )_     e#     Increment and duplicate.
    N),2>  e#     Push [2 3 ... N].
    f%     e#     Take the current value modulo each of these.
    s      e#     Flatten them into a single string.
    _W%    e#     Duplicate and reverse.
    #      e#     Try to find the reverse in the original. A common way to compute
           e#     "not equal" for strings of the same length.
  }g
  _p       e#   Print a copy of the result.
}*
;          e# Discard the final result to prevent printing it twice.
\$\endgroup\$
1
\$\begingroup\$

PHP, 93 Bytes

for(;$x<$a=$argn;$s="")for($i=1,++$n;$i++<$a;)if($i==$a&strrev($s.=$n%$i)==$s)echo$n._.!++$x;

Online Version 2 Loops Output as string

Expanded

for(;$x<$a=$argn;$s="") 
for($i=1,++$n;$i++<$a;)
    if($i==$a&strrev($s.=$n%$i)==$s)echo$n._.!++$x; 

PHP 130 Bytes

for(;count($r)<$a=$argn;$s=[])for($i=1,++$n;$i++<$a;){$s[]=$n%$i;if(count($s)==$a-1&strrev($j=join($s))==$j)$r[]=$n; }print_r($r);

Online Version 2 Loops

Expanded

for(;count($r)<$a=$argn;$s=[])
for($i=1,++$n;$i++<$a;){
    $s[]=$n%$i;
    if(count($s)==$a-1&strrev($j=join($s))==$j)$r[]=$n; 
}
print_r($r);

PHP, 139 Bytes with 1 loop

for($i=$n=1;count($r)<($a=$argn)&$i++<$a;){$s[]=$n%$i;if(count($s)==$a-1){if(strrev($j=join($s))==$j)$r[]=$n;$n++;$s=[];$i=1;}}print_r($r);

Online Version 1 Loop

Run with

echo '<string>' | php -nR '<code>'

Expanded

for($i=$n=1;count($r)<($a=$argn)&$i++<$a;){
    $s[]=$n%$i;
    if(count($s)==$a-1){
        if(strrev($j=join($s))==$j)$r[]=$n;
        $n++;
        $s=[];
        $i=1;
    }
}
print_r($r);
\$\endgroup\$
1
\$\begingroup\$

QBIC, 48 bytes

:{A=G[2,a|A=A+!q%b$]~A=_fA||h=h+1?q]q=q+1~h=a|_X

Beats Mathematica! Sample run:

Command line: 10
 1 
 280 
 281 
 560 
 1611 
 1890 
 1891 
 2170 
 2171 
 2241 

Explanation:

:{          Get 'a' from the command line, start an inf. loop
A=G         Clear out whatever's in A$
[2,a|       For each of the numbers we want to modulo
A=A+        Add to A$ 
     q%b       our current number MODULO te loop iterator
    !   $      cast to string
]           NEXT
~A=_fA|     If the string of remainders is a palindrome (_f ... | is Reverse())
|h=h+1      THEN h=h+1 (h starts at 0) - this counts how many hits we've had
 ?q            also, print the number with the palindromic remainder
]           END IF
q=q+1       Test the next number
~h=a|_X     If we've had 'a' hits, quit.
            The last IF and the infinite loop are closed implicitly.
\$\endgroup\$
1
\$\begingroup\$

Japt, 26 bytes

L³o fR{C=Uò2@R%Xì ¥CwÃj1U

Try it online! Takes a few seconds on all inputs, so be patient please.

This would be considerably shorter (and faster) if there were a built-in to get the first N numbers satisfying some condition:

R{C=Uò2@R%Xì ¥Cw}aU
\$\endgroup\$

Your Answer

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

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